java - 为什么这个 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再次。

此外，无需检查 visited[i] == 0推前i入栈。当i将从堆栈中弹出(稍后)，代码将检查其访问状态。

更新

(a) 输入 ( arr ) 不反射(reflect)问题开始时呈现的图表。需要修改为:

  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--) {

应用这些修复后，输出将变为:

0
1
3
5
4
2