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

I am trying to use recursion and a 2D array to implement a Depth First Search on an adjacency matrix and having issues. I'm still new to this, sorry if my mistake is too obvious.

我试图使用递归和2D数组在邻接矩阵上实现深度优先搜索并遇到问题。我还是新手,对不起,如果我的错误太明显了。

My code does not read the row if all the numbers are all 0 and doesn't show the components visited.

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

For example a 10x10 martrix that only has 1s on row, column (9,6) and also (6,9) respectively. Everything else is 0.

例如,10x10 martrix在行,列(9,6)和(6,9)上分别只有1。其他一切都是0。

It should output

它应该输出

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

Here is my method so far.

到目前为止,这是我的方法。

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
            }
        }
    }   
}

THe only thing that the above displays is Component 1 and then the method stops.

上面显示的只是组件1,然后方法停止。

1 个解决方案

#1

In your example, there is no connect between the first node and other nodes. Hence, we can't go anywhere from the first node.

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

The code should be something like this:

代码应该是这样的:

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);
}

#1