Реализация DFS по путям Эйлера

Question

Я реализую алгоритм, чтобы найти все пути Эйлера в графе.Я основываюсь на создании dfs в коде, найденном здесь: Найти все возможные циклы Эйлера

Вот мой текущий код:

public class Graph {

private int numVertex;
private int numEdges;
private boolean[][] adj;

public Graph(int numVertex, int numEdges) {
    this.numVertex = numVertex;
    this.numEdges = numEdges;
    this.adj = new boolean[numVertex+1][numVertex+1];
}

public void addEdge(int start, int end){
    adj[start][end] = true;
    adj[end][start] = true;
}

public Integer DFS(Graph G, int startVertex){
    int i=0;
    pilha.push(startVertex);
    for(i=0; i<G.numVertex; i++){

        if(G.adj[i][startVertex] != false){
            System.out.println("i: " + i);
            G.adj[i][startVertex] = false;
            G.adj[startVertex][i] = false;

            DFS(G, i);

            G.adj[i][startVertex] = true;
            G.adj[startVertex][i] = true;
        }

    }
    return -1;
}

Stack<Integer> pilha = new Stack();

public static void main(String[] args) {

    Scanner input = new Scanner(System.in);

    int numVertices = input.nextInt();
    int numLinks = input.nextInt();
    int startNode = input.nextInt();

    Graph g = new Graph(numVertices, numLinks);

    for(int i = 0; i<numLinks; i++){
        g.addEdge(input.nextInt(),input.nextInt());
    }

}

}

К сожалению, я не получаю правильных результатов и не могу понять, почему.Я много чего пробовал, как сохранить результаты из dfs в списке и распечатать их, но все же у меня нет путей.

Любая идея о том, как я могу изменить свой код, чтобы я начал получать эйлерпути?

Answer 1

Что вы ожидаете от вашей программы?Вы помещаете узлы во временный стек (pilha).Вам нужно сохранить этот стек, потому что он фактически определит порядок, в котором вы должны посещать узлы.Также метод DFS является недействительным, но каким-то образом вы добавляете результат его вызова в список res.Этот код даже успешно работает?