使用邻接矩阵进行深度优先搜索？

Question

我正在尝试使用递归和二维数组在邻接矩阵上实现深度优先搜索，但遇到了问题。我还是个新手，如果我的错误太明显了，抱歉。

如果所有数字都为 0 并且不显示访问的组件，我的代码不会读取该行。

例如，一个 10x10 矩阵，其行、列 (9,6) 和 (6,9) 分别只有 1。其他都是 0。

它应该输出

Component: 1
Component: 2
Component: 3
Component: 4
Component: 5
Component: 6 9
Component: 7
Component: 8
Component: 10
Total number of Components: 9

这是我目前的方法。

public static void dfs(int i, int[][] G) {
    boolean [] visited = new boolean[10];

    if(!visited[i]){        
        visited[i] = true; // Mark node as "visited"
        System.out.println("Compnent: " );
        System.out.println( i+1 + " ");

        for (int j = 0; j < G[i].length-1; j++) {
            if (G[i][j]==1 && !visited[j]) {   
                dfs(j, G); // Visit node
            }
        }
    }   
}

以上显示的唯一内容是组件 1，然后该方法停止。

Answer 1

在您的示例中，第一个节点与其他节点之间没有连接。因此，我们不能从第一个节点去任何地方。

代码应该是这样的：

public static void dfs(int i, int[][] graph, boolean[] visited) {
    if(!visited[i]){        
        visited[i] = true; // Mark node as "visited"
        System.out.print(i+1 + " ");

        for (int j = 0; j < graph[i].length; j++) {
            if (graph[i][j]==1 && !visited[j]) {   
                dfs(j, graph, visited); // Visit node
            }
        }
    }   
}

public static void main(String[] args) {
    // your matrix declare
    boolean [] visited = new boolean[10];
    int count = 0;
    for(int i = 0; i < graph.length; i++) {
        if(!visited[i]) {
            System.out.println("Compnent: " );
            dfs(i,graph,visited);
            ++count;
        }
    }
    System.out.println("Total number of Components: " + count);
}

使用邻接矩阵进行深度优先搜索？

Depth First Search using Adjacency Matrix?

java

recursion

multidimensional-array

depth-first-search

adjacency-matrix