爲什麼這個DFS代碼在某些情況下不起作用？

Question

根據上面的圖片DFS應該是：（？這是一個情況下，只有發生，我做錯了什麼）0 1 3 5 4 2但它的返回0 1 3 5 2

代碼：

import java.util.Stack; 

public class DFSDetectCycleSelf { 

static int arr[][] = { 
     { 0, 1, 1, 0, 0, 0 }, 
     { 0, 0, 0, 1, 0, 0 }, 
     { 0, 0, 0, 0, 0, 0 }, 
     { 0, 0, 0, 0, 0, 1 }, 
     { 0, 0, 0, 0, 0, 0 }, 
     { 0, 0, 0, 0, 1, 0 } 
     //working fine for static int arr[][]={{0,1,1,0,0,0}, 
     // {0,0,0,1,1,0}, 
     //{0,0,0,0,0,1}, 
     //{0,0,0,0,0,0}, 
     //{0,0,0,0, 0,0}, 
     //{0,0,0,0,0,0}}; 
static Stack<Integer> stack; 

DFSDetectCycleSelf(){ 
    stack = new Stack<Integer>(); 
} 

public static void main(String[] args){ 
    DFSDetectCycleSelf df = new DFSDetectCycleSelf(); 
    PrintDFS(); 

} 

public static void PrintDFS(){ 
    int source = 0; 
    int numberOfNodes = arr[source].length; 
    int [] visited = new int[numberOfNodes]; 
    int v; 
    stack.push(source); 


    while (!stack.isEmpty()){ 
     v = stack.pop(); 
     if(visited[v]==0) { 
      visited[v] = 1; 
      System.out.println(v); 
     } 

     for(int i=0;i<numberOfNodes;i++){ 
      if(arr[v][i]==1 && visited[i]==0){ 
       stack.push(v); 
       System.out.println(i); 
       visited[i]=1; 
       v = i; 
      } 
     } 

    } 
} 

}

Answer 1

這應該工作：

public static void PrintDFS(){ 
    int source = 0; 
    int numberOfNodes = arr[source].length; 
    int [] visited = new int[numberOfNodes]; 
    int v; 
    stack.push(source); 


    while (!stack.isEmpty()){ 
     v = stack.pop(); 
     if(visited[v]==0) { 
      visited[v] = 1; 
      System.out.println(v); 
      for(int i=0;i<numberOfNodes;i++){ 
      if(arr[v][i]==1) 
       stack.push(i); 
      } 
     } 
    } 
} 

原始代碼中的主要問題是在for循環中：當arr[v][i] == 1這意味着iv的鄰居。您不應將i放入堆棧，而應將v放入v的鄰居，而不要再次訪問v。

另外，在將i推入堆棧之前，不需要檢查visited[i] == 0。當i將從棧中彈出（稍後）時，代碼將檢查其訪問狀態。

更新

（一）輸入端（arr）不反映在問題的開始呈現的曲線圖。它需要更改爲：

static int arr[][] = { 
    { 0, 1, 1, 0, 0, 0 }, 
    { 0, 0, 0, 1, 0, 0 }, 
    { 0, 0, 0, 0, 0, 0 }, 
    { 0, 0, 0, 0, 0, 1 }, 
    { 0, 0, 0, 0, 0, 0 }, 
    { 0, 0, 0, 0, 1, 0 } 
    }; 

（b）如果邊緣是有序的（在這個意義上邊緣(x) -> (y)應邊緣(x) -> (y+1)前走過），那麼確實，正如亞歷克西斯Ç早些時候提出的，換循環需要往回走

for (int i = numberOfNodes - 1; i >= 0; i--) { 

其中一個修補程序應用的輸出變爲：

0 
1 
3 
5 
4 
2 

Answer 2

與您的代碼的問題是

... 
v = i; // shouldn't be there 
... 

這是一般情況下的迭代算法訪問所有節點的圖形

WHILE there exists a graph node not marked loop 
    Find an unmarked node F 
    Add node F to collection (stack or queue) 
    WHILE the collection is not empty loop 
     Remove a node N from the collection 
     IF the node N is unmarked 
      Mark node N 
      Add all adjacent nodes of node N to the collection 
      Process node N 

收集取決於你需要解決的問題。如果通過查看最短路徑來解決問題，隊列（意思是BFS）就是要走的路。如果問題能夠通過了解迷宮中的路線來解決，堆棧（意味着DFS）就可以走了。此外，在樹的情況下（就像在這個問題中），你知道根節點，算法的前兩行是不必要的。

內部循環的一個重要部分是準備相鄰節點的未來處理，但重要的是不要跟隨那些鏈接到相鄰節點，並且通過跟隨鏈接來更改節點。因爲這些節點被放置在集合中並且將來將被處理，所以沒有必要遵循該鏈接。

內部循環的作用只着重於節點N.這種問題的劃分有助於簡化算法，並且更容易執行更大的任務，即只訪問和處理所有節點一次。