深度優先搜索使用鄰接矩陣？

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