为什么这个 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 时，它意味着 i 是 v 的邻居。你不应该将 i 压入堆栈而不是 v：你想访问 v 的邻居而不是再次访问 v。

此外，在将 i 压入堆栈之前无需检查 visited[i] == 0。当 i 将从堆栈中弹出时（稍后），代码将检查其访问状态。

更新

(a) 输入 (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) 之前被遍历）那么实际上，正如 Alexis C 之前所建议的那样，for 循环需要倒退

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

应用这些修复后输出变为：

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

collection取决于您需要解决的问题。如果通过查看最短路径来解决问题，那么队列（意思是 BFS）就是要走的路。如果问题可以通过了解迷宫中的路线来解决，那么堆栈（意思是 DFS）就可以解决。此外，对于您知道根节点的树（如本题），算法的前两行是不必要的。

内循环的一个重要部分是为以后处理相邻节点做准备，但重要的是不要跟随那些link到相邻节点并且v = i;改变节点以下 link。 link后面没有必要，因为那些节点放在collection里面，以后再处理。

内循环的作用是只强调节点N。这种问题划分有助于简化算法，并使其更容易执行更大的任务，即只访问和处理所有节点一次。

为什么这个 DFS 代码在某些情况下不起作用？

Why this DFS code is not working in some cases?

java

microsoft-distributed-file-system

data-structures