用java回溯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][numVertex]; 
    } 

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

    List<Integer> visited = new ArrayList<Integer>(); 

    public Integer DFS(Graph G, int startVertex){ 
     int i=0; 

     if(pilha.isEmpty()) 
      pilha.push(startVertex); 

     for(i=1; i<G.numVertex; i++){ 
      pilha.push(i); 
      if(G.adj[i-1][startVertex-1] != false){ 
       G.adj[i-1][startVertex-1] = false; 
       G.adj[startVertex-1][i-1] = false; 
       DFS(G,i); 
       break; 
      }else{ 
       visited.add(pilha.pop()); 
      } 
      System.out.println("Stack: " + pilha); 
     } 
     return -1; 
    } 

    Stack<Integer> pilha = new Stack(); 

    public static void main(String[] args) { 

     Graph g = new Graph(6, 9); 

     g.addEdge(1, 2); 
     g.addEdge(1, 5); 
     g.addEdge(2, 4); 
     g.addEdge(2, 5); 
     g.addEdge(2, 6); 
     g.addEdge(3, 4); 
     g.addEdge(3, 5); 
     g.addEdge(4, 5); 
     g.addEdge(6, 4); 

     g.DFS(g, 1);  

    } 
} 

我試圖解決歐拉路徑問題。該程序解決了基本的圖形，但是當它需要回溯時，它只是沒有做到這一點。我認爲這個問題可能出現在堆棧操作或遞歸dfs調用中。我嘗試了很多東西，但似乎無法弄清楚爲什麼它不會回溯。有人能幫助我嗎？

Answer 1

我只測試過一個，所以不要相信我的代碼。

public class Graph { 
    private int numVertex; 
    private boolean[][] adj; 

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

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

    List<Integer> visited = new ArrayList<Integer>(); 
    public void DFS(Graph G, int startVertex){ 
     int i=0; 
     pilha.push(startVertex); 

     while (!pilha.empty()) { 
      int v = pilha.peek(); 
      Boolean hasNeighbor = false; 
      for (i = 1; i <= G.numVertex; i++) { 
       if(G.adj[i-1][v-1] != false) { 
        hasNeighbor = true; 
        pilha.push(i); 
        G.adj[i-1][v-1] = false; 
        G.adj[v-1][i-1] = false; 
        break; 
       } 
      } 
      if (!hasNeighbor) { 
       visited.add(0, pilha.pop()); 
      } 
     } 
     System.out.println("Path: " + visited); 
    } 

    Stack<Integer> pilha = new Stack<Integer>(); 

    public static void main(String[] args) { 
     Graph g = new Graph(6, 9); 
     g.addEdge(1, 2); 
     g.addEdge(2, 3); 
     g.addEdge(3, 4); 
     g.addEdge(4, 5); 
     g.addEdge(5, 6); 
     g.addEdge(6, 4); 
     g.addEdge(4, 2); 
     g.addEdge(2, 1); 
     g.DFS(g, 1);  
    } 
} 

此外，而不是多次張貼同樣的問題，當你試圖解決這個問題，你應該修改了同樣的問題。

Answer 2

這是DFS的正確版本。並替換訪問List至hashset。

Set<Integer> visited = new HashSet<Integer>(); 

public Integer DFS(Graph G, int startVertex){ 
    int i=0; 

    visited.add(startVertex); 

    if(visited.size() == G.numVertex){ 
     System.out.println("FOUND PATH"); 
     System.out.println("Stack: " + pilha); 
     return 1; 
    } 
    int result = -1; 
    if(pilha.isEmpty()) 
     pilha.push(startVertex); 



    for(i=1; i<=G.numVertex; i++){ 
     if(G.adj[startVertex-1][i-1] == true && visited.contains(i) == false){ 
      pilha.push(i); 
      //visited.add(i); 
      result = DFS(G, i); 
      if(result == 1){ 
       return 1; 
      } 
      pilha.pop(); 
      //visited.remove(i); 
     } 
     System.out.println("Stack: " + pilha); 
    } 

    visited.remove(startVertex); 

    return result; 
}