使用邻接表检查有向图是否强连通

Question

我需要查明给定的邻接表 (int[][]) 是否描述了强连通图。我在图中有超过 2 个节点的一些测试用例失败了。例如 adjlist = new int[][] {{ 1 },{ 2 },{ 0 },};这意味着节点 0（列表中的第一个）可以连接到节点 1，节点 1 可以连接到节点 2，节点 2 可以连接到节点 0。我试过这个：

 public boolean allDevicesConnected(int[][] adjlist) {
     Boolean[] visited = new Boolean[adjlist.length];
     for (int i = 0; i < adjlist.length; i++) {
         for (int b = 0; b < visited.length; b++) {
             visited[b] = false;
         }
         DFS1( adjlist, i, visited);
     }
        for (int j = 0; j < visited.length; j++) {
            if (visited[j] == false) {
                return false;
         }
     }   
     return true;
}
 
 private static void DFS1(int[][] adjlist, int v, Boolean[] visited) {
    visited[v] = true;
    for (int i = 0; i < adjlist[v].length; i++) {
        if (visited[i] == false) {
            DFS1(adjlist, i, visited);
        }
    }
}

如有帮助将不胜感激！！

Answer 1

你的想法是使用深度优先搜索，同时将节点标记为已访问以确定是否强连接是一个好主意。

不需要第一个双循环。如果图实际上是强连通的，那么我们从哪个节点开始并不重要。

首先，我注意到您在 DFS 搜索中这样做：

visited[i] == false

和

DFS1(adjlist, i, visited);

就是说，当您执行此操作时，您没有检查正确的节点。您应该检查的不是索引 i，而是存储在索引 i 处的节点的实际值。

我编辑了你的代码以使用这个想法：

public boolean allDevicesConnected(int[][] adjlist){
    boolean[] marked = new boolean[adjlist.length];  // Default is set to false  

    DFS_helper(0, adjlist, marked);

    for(boolean b : marked)
        if(b == false) return false;

    return true;
}

public void DFS_helper(int node, int[][] adjlist, boolean[] marked){
    marked[node] = true;

    for (int i = 0; i < adjList[node].length; i++) {
        int dest = adjlist[node][i];
        if(marked[dest] == false)
            DFS_helper(dest, adjlist, marked);
    }

}

使用邻接表检查有向图是否强连通

Check if directed graph is strongly connected using adjacency list

java

algorithm

graph