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

Question

我想使用递归和二维数组来实现深度优先搜索的邻接矩阵和有问题。我仍然对此感到陌生，不好意思，如果我的错误太明显了。

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

例如，10x10 martrix在行，列（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); 
}