如何檢查Graph是否連接

Question

我有一個無向圖，並且想知道一個節點是否連接到另一個節點？

例如

0 1 0 
1 0 1 
0 1 0 

在該節點1被連接到節點3（因爲有從1到2和2至3個，因此1-3被連接的路徑）

我已經寫使用DFS的程序，但我無法弄清楚爲什麼會給出錯誤的結果。

我不想讓任何全局變量，並希望我的方法返回true ID節點使用遞歸程序

public static boolean isConnectedGraph(int[][] graph, int start, int end, 
     int visited[]) { 
    visited[start] = 1; 
    if (graph[start][end] == 1) { 
     System.out.println("Yes connected...."); 
     return true; 
    } 
    for (int i = 0; i < graph[0].length; i++) { 
     if (graph[start][i] == 1 && visited[i] == 0) { 
      visited[i] =1; 
      isConnectedGraph(graph, i, end, visited); 

     } 
    } 
    return false; 
} 

Answer 1

你不的結果做任何連接遞歸調用isConnectedGraph(graph, i, end, visited);。你應該把它分配給一個變量，如果它是true - 返回true。

更改主循環是這樣的：

for (int i = 0; i < graph[0].length; i++) { 
    if (graph[start][i] == 1 && visited[i] == 0) { 
     visited[i] =1; 
     if (isConnectedGraph(graph, i, end, visited)) return true; 

    } 
}