使用邻接矩阵的图的 DFS (Java)

Question

您好，我的代码在执行深度优先遍历时显示错误的顺序时遇到问题

class graphs{

public static void main(String [] args){
    int[][] adjMatrix = { {0, 1, 0, 0, 1, 1, 0, 0},
            {1, 0, 0, 0, 0, 1, 1, 0},
            {0, 0, 0, 1, 0, 0, 1, 0},
            {0, 0, 1, 0, 0, 0, 0, 1},
            {1, 0, 0, 0, 0, 1, 0, 0},
            {1, 1, 0, 0, 1, 0, 0, 0},
            {0, 1, 1, 0, 0, 0, 0, 1},
            {0, 0, 0, 1, 0, 0, 1, 0}};
    boolean[] visited = {false, false, false, false, false, false, false, false};
    int n = 8;

    DFS(adjMatrix, visited, n, 0);
}

public static void DFS(int[][] adjMatrix, boolean [] visited,int n, int i){
    System.out.print(" " + (i+1));
    visited[i]= true;
    for (int j = 0; j<n;j++){
        if(!(visited[j]) && adjMatrix[i][j]==1){
            DFS(adjMatrix, visited, n, j);
        }

    }
  }
}

我被告知我应该得到：1 2 6 7 4 3 5 8

然而，我不断得到：1 2 6 5 7 3 4 8

我做错了什么？

编辑：它应该显示访问的顺序。也许这就是我搞砸的地方？

编辑：另外，我怎样才能让它显示死胡同的顺序？

对于死胡同，像这样的工作：

public static void DFS(int[][] adjMatrix, boolean [] visited,int n, int i){
System.out.print(" " + (i+1));
visited[i]= true;
for (int j = 0; j<n;j++){
    if(!(visited[j]) && adjMatrix[i][j]==1){
        DFS(adjMatrix, visited, n, j);
    }

}
a.add(i+1); //assume a is an integer ArrayList and will be printed out later
}

Answer 1

你被告知错了，你的输出是正确的。

你可以手查：

       1  2  3  4  5  6  7  8
    1 {0, 1, 0, 0, 1, 1, 0, 0}
    2 {1, 0, 0, 0, 0, 1, 1, 0}
    3 {0, 0, 0, 1, 0, 0, 1, 0}
    4 {0, 0, 1, 0, 0, 0, 0, 1}
    5 {1, 0, 0, 0, 0, 1, 0, 0}
    6 {1, 1, 0, 0, 1, 0, 0, 0}
    7 {0, 1, 1, 0, 0, 0, 0, 1}
    8 {0, 0, 0, 1, 0, 0, 1, 0}

你只需 "jump" 直到找到 0，我们从 1 开始，第一行中的第一个 1 在标记为 2 的列中，我们移动到第 2 行，第 2 行中的第一个 1 not yet visited/is not being visited currently is at 6, we move to row 6, again the first interesting 1 is at 5, we move to row 5, there are no interesting 1s in that row as we currently on a已经访问过 1 和 6 的路径，所以我们回溯，此时我们有 1,2,6,5。我们回溯到第 2 行，第一个有趣的 1 在第 7 行，在第 7 行我们得到 3，在第 3 行我们转到第 4，然后回溯到第 7 行并转到 8，这将用您的结果完成所有节点。

@Edit：只是为了弄清楚其他答案可能使用 DFS 是可能的（取决于您处理邻居的顺序）但您应该提供的答案是这个输入绝对不可能。

@Edit：准确地说是 1 -> 2 -> 6 -> 5 -> backtrack(2) -> 7 -> 3 -> 4 -> 8 -> end

Answer 2

根据您的矩阵，adjMatrix[6][5] = 1 但 adjMatrix[6][7] = 0，因此您预期的答案 1 2 6 7 4 3 5 8 不正确，因为没有 link在6到7之间。你应该再次检查输入数据，很可能你输入错误。

使用邻接矩阵的图的 DFS (Java)

DFS of a graph using an adjacency matrix (Java)

java

depth-first-search