DFSバックトラックwith java

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

私はこれを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; 
}