java - 欧拉路径 DFS 实现

Question

我正在实现一种算法来查找图中的所有欧拉路径。我以自己为基础，在此处找到的代码中创建 dfs:Find all possible Euler cycles

这是我当前的代码:

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 中。这段代码能成功运行吗？