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

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}

您只需"跳转"直到找到 0，我们从 1 开始，第一行的前 1 在标记为 2 的列处，我们移动到第 2 行，第 2 行中尚未访问/当前未被访问的前 1 在 6，我们移动到第 6 行，再次第一个有趣的 1 在 5， 我们移动到第 5 行，该行中没有有趣的 1，因为我们目前在已经访问过 1 和 6 的路径上，所以我们回溯，此时我们有 1,2,6,5。我们回溯到第 2 行，第一个有趣的 1 在 7 处，在第 7 行我们得到 3，在第 3 行我们回溯到 4，然后回溯到 7 并转到 8，用您的结果完成所有节点。

@Edit：只是为了明确一点，DFS可能会提供其他答案（取决于你将处理邻居的顺序），但你应该提供的答案绝对不可能用于此输入。

@Edit：所以准确地说，应该是 1 -> 2 -> 6 -> 5 ->回溯（2）

Answer 2

基于您的矩阵，adjMatrix[6][5] = 1

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