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

Question

 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

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

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

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

visited[i] == false

DFS1(adjlist, i, visited);

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

}