Случайно сгенерированные графики для вывода пути Эйлера или цикла Эйлера для него - PullRequest
Новая
       18

Случайно сгенерированные графики для вывода пути Эйлера или цикла Эйлера для него

0 голосов
/ 28 января 2020

У меня есть этот код в Java. Он может напечатать путь Эйлера или цикл для заданных графиков, используя алгоритм Флери. Моя цель состоит в том, чтобы изменить этот код для печати путей или схем Эйлера, используя только случайно сгенерированные графы. Кроме того, я хотел бы, чтобы он печатал только минимальные циклы Эйлера, но основная цель - это случайная генерация для графов. 

import java.util.ArrayList; 

public class Graph { 

    private int vertices; 
    private ArrayList<Integer>[] adj; 

    Graph(int numOfVertices) 
    { 
        this.vertices = numOfVertices; 

        initGraph(); 
    } 

    @SuppressWarnings("unchecked") 
    private void initGraph() 
    { 
        adj = new ArrayList[vertices]; 
        for (int i = 0; i < vertices; i++)  
        { 
            adj[i] = new ArrayList<>(); 
        } 
    } 

    private void addEdge(Integer u, Integer v) 
    { 
        adj[u].add(v); 
        adj[v].add(u); 
    } 

    private void removeEdge(Integer u, Integer v) 
    { 
        adj[u].remove(v); 
        adj[v].remove(u); 
    } 

    private void printEulerTour() 
    { 
        Integer u = 0; 
        for (int i = 0; i < vertices; i++) 
        { 
            if (adj[i].size() % 2 == 1) 
            { 
                u = i; 
                break; 
            } 
        } 

        printEulerUtil(u); 
        System.out.println(); 
    } 

    private void printEulerUtil(Integer u) 
    { 
        for (int i = 0; i < adj[u].size(); i++) 
        { 
            Integer v = adj[u].get(i); 
            if (isValidNextEdge(u, v))  
            { 
                System.out.print(u + "-" + v + " "); 

                removeEdge(u, v);  
                printEulerUtil(v); 
            } 
        } 
    } 

    private boolean isValidNextEdge(Integer u, Integer v) 
    { 
        if (adj[u].size() == 1) { 
            return true; 
        } 

        boolean[] isVisited = new boolean[this.vertices]; 
        int count1 = dfsCount(u, isVisited); 

        removeEdge(u, v); 
        isVisited = new boolean[this.vertices]; 
        int count2 = dfsCount(u, isVisited); 

        addEdge(u, v); 
        return (count1 > count2) ? false : true; 
    } 

    private int dfsCount(Integer v, boolean[] isVisited) 
    { 
        isVisited[v] = true; 
        int count = 1; 
        for (int adj : adj[v]) 
        { 
            if (!isVisited[adj]) 
            { 
                count = count + dfsCount(adj, isVisited); 
            } 
        } 
        return count; 
    } 

    public static void main(String a[]) 
    {  
        //My graphs

        Graph g1 = new Graph(5); 
        g1.addEdge(1, 0); 
        g1.addEdge(0, 2); 
        g1.addEdge(2, 1); 
        g1.addEdge(0, 3); 
        g1.addEdge(3, 4); 
        g1.addEdge(3, 2); 
        g1.addEdge(3, 1); 
        g1.addEdge(2, 4);
        g1.printEulerTour(); 
    } 
}

Есть идеи, как я могу реализовать случайную генерацию для графов здесь?

...