时间戳

首页 > 解决方案 > 使用邻接表检查有向图是否强连接

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

问题描述

我需要找出给定的邻接列表（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);
        }
    }
}

任何帮助都会非常感谢！

标签： javaalgorithmgraph

解决方案

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

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

首先，我注意到您在 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);
    }

}

推荐阅读