检查有向图是否强连通的算法

StackOverflow https://stackoverflow.com/questions/1434787

题

我需要检查有向图是否是 强关联, ，或者换句话说，如果任何其他节点都可以到达所有节点（不一定通过直接边）。

实现此目的的一种方法是在每个节点上运行 DFS 和 BFS，并查看所有其他节点是否仍可访问。

有更好的方法吗？

有帮助吗？

解决方案

Tarjan's 强关联组件算法（或 Gabow的变体）当然就足够了;如果只有一个强连接组件，则图形连接很强。

两者都是线性时间。

与正常深度优先搜索一样，您可以跟踪每个节点的状态：新节点，已查看但仍处于打开状态（它位于调用堆栈中），并且已查看并已完成。此外，您可以在第一次到达节点时存储深度，以及从节点可以访问的最低深度（在完成节点后就知道了这一点）。如果最低可达深度等于其自身深度，则节点是强连接组件的根。即使您从根到达节点的深度不是最小可能的深度，这也可以工作。

要检查整个图是否是单个SCC，请从任何单个节点启动dfs，当您完成时，如果最低可达深度为0，并且每个节点都被访问过，那么整个图是强烈联系。

其他提示

考虑以下算法。

  1. 从随机顶点开始 v 图表的 G, ，并运行 DFS(G, v).

    • 如果 DFS(G, v) 无法到达图中的所有其他顶点 G, ，那么有一些顶点 u, ，这样就没有从 v 到 u, ， 因此 G 是 不强连接.

    • 如果它确实到达每个顶点，则存在一条有向路径 v 到图中的每个其他顶点 G.

  2. 反转有向图中所有边的方向 G.

  3. 再次运行 DFS 开始于 v.

    • 如果 DFS 未能到达每个顶点，则存在某个顶点 u, ，这样在原始图中就没有来自的有向路径 u 到 v.

    • 另一方面，如果它确实到达每个顶点，那么在原始图中 从每个顶点都有一条有向路径 u 到 v.

因此，如果 G“通过”两个 DFS，则它是强连通的。此外，由于 DFS 运行在 O(n + m) 时间，该算法运行在 O(2(n + m)) = O(n + m) 时间，因为它需要 2 次 DFS 遍历。

检查每个节点是否同时具有指向给定图形中每个其他节点的路径：

1。所有节点的DFS / BFS：

Tarjan的算法假设每个节点都有一个深度d[i]。最初，根的深度最小。我们为d[i] = min(d[j]) j的任何邻居进行订单后DFS更新i。实际上BFS也适用于减少规则u这里。

function dfs(i)
    d[i] = i
    mark i as visited
    for each neighbor j of i: 
        if j is not visited then dfs(j)
        d[i] = min(d[i], d[j])

如果存在从v到d[u] <= d[v]的转发路径，则d[v] <= d[u] <= d[v]。因此，在SCC中，，SCC中的所有节点将具有相同的深度。要判断图形是否为SCC，我们检查所有节点是否具有相同的<=>。

2。来自单个节点的两个DFS / BFS：

它是 Kosaraju <！>＃8217; s算法的简化版本。从根开始，我们检查DFS / BFS是否可以访问每个节点。然后，反转每个边缘的方向。我们检查是否可以再次从同一个根到达每个节点。请参阅 C ++代码。

您可以计算所有对最短路径，看看是否有无限的

已经提到了Tarjan的算法。但我经常发现 Kosaraju的算法更容易理解，即使它需要两次遍历图表。 IIRC，在CLRS中也很好地解释了它。

test-connected(G)
{
    choose a vertex x
    make a list L of vertices reachable from x,
    and another list K of vertices to be explored.
    initially, L = K = x.

    while K is nonempty
    find and remove some vertex y in K
    for each edge (y, z)
    if (z is not in L)
    add z to both L and K

    if L has fewer than n items
    return disconnected
    else return connected
}

这样做的一种方法是为图表生成拉普拉斯矩阵，然后计算特征值，最后计算零的数量。如果只存在一个零特征值，则图形是强连接。

注意：注意为有向图创建拉普拉斯矩阵的方法略有不同。

你可以使用Kosaraju <！>＃8217;基于DFS的简单算法，它可以执行两次DFS遍历图：

这个想法是，如果每个节点都可以从顶点v到达，并且每个节点都可以到达v，那么图形就是强连接的。 在算法的第2步中，我们检查是否可以从v到达所有顶点。在步骤4中，我们检查所有顶点是否都可以到达v（在反向图中，如果所有顶点都可以从v到达，那么所有顶点都可以达到v原始值图）。

算法： 1）将所有顶点初始化为未访问。

2）从任意顶点开始对图进行DFS遍历v。如果DFS遍历没有<！>＃8217; t访问所有顶点，则返回false。

3）反转所有弧线（或找到图形的转置或反转）

4）在反转图中将所有顶点标记为未访问。

5）从相同的顶点v开始执行反向图的DFS遍历（与步骤2相同）。如果DFS遍历没有<！>＃8217; t访问所有顶点，则返回false。否则返回true。

时间复杂度：如果使用邻接列表表示来表示图形，则上述实现的时间复杂度与深度优先搜索相同，即O（V + E）。

许可以下： CC-BY-SA 和 归因
不隶属于 StackOverflow
scroll top