歐拉路徑DFS實現

我正在實現一種算法來查找圖中的所有歐拉路徑。我自己的基礎，創造了DFS，在代碼中發現的位置：Find all possible Euler cycles 歐拉路徑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的結果存儲在列表中並打印出來，但仍然沒有路徑。

任何想法如何修改我的代碼，讓我開始獲得歐拉路徑？

來源

2012-03-22 Cláudio Ribeiro

你認爲你的程序的結果是什麼？您正在將節點推到臨時堆棧（pilha）。您需要保留該堆棧，因爲它實際上會確定您應該訪問節點的順序。此外，DFS方法是無效的，但不知何故，您將其調用結果添加到列表res中。這段代碼是否能夠成功運行？

來源

2012-03-22 11:59:38

對不起，當我添加它時，代碼有點笨拙。我會盡量把它清理一下。 – 2012-03-22 12:08:08

目前尚不清楚。隨着新的變化，沒有理由讓DFS返回一個整數。莫名其妙地用pilha。 – 2012-03-22 12:56:20

我可能需要將dfs與堆棧一起運行，以便我可以回溯它。但就目前而言，我可以在圖表中執行DFS搜索。 – 2012-03-22 13:19:53

歐拉路徑DFS實現

回答

相關問題