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

Question

我需要检查一个有向图是否强连通，也就是说，任何一个节点都可以通过其他节点到达（不一定是通过直接边缘）。

一种方法是在每个节点上运行DFS和BFS，并查看所有其他节点是否仍然可达。

是否有更好的方法来做到这一点？

- Kazoom

---

我认为普遍接受的称呼是“有向图”，而不是“方向性图”。 - Aryabhatta

Answer 1

考虑以下算法。

---

1. 从图 G 中的一个随机顶点 v 开始，运行 DFS(G, v)。

   • 如果 DFS(G, v) 无法到达图 G 中的其他每个顶点，则存在某个顶点 u，使得从 v 到 u 没有有向路径，因此 G 不是强连通的。

   • 如果它能够到达每个顶点，则从 v 到图 G 中的每个其他顶点都存在一条有向路径。

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

3. 再次从 v 开始运行 DFS。

   • 如果 DFS 未能到达每个顶点，则在原始图中存在一些顶点 u，使得从 u 到 v 没有有向路径。

   • 另一方面，如果它能够到达每个顶点，则在原始图中存在一条从每个顶点 u 到 v 的有向路径。

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

- AliP

---

不错！与Kosaraju算法寻找强连通分量非常相似。 - codewarrior

@Alip - 两个问题：(1)我们可以在你的算法中使用BFS(G, v)代替DFS(G,v)吗？(2)为了判断DFS是否能够从v到达每个顶点，我们可以保持一个访问过的顶点计数器c，然后比较c == |G.V|吗？ - KGhatak

Answer 2

Tarjan算法和Gabow算法都可以用于查找有向图的强连通分量。如果只有一个强连通分量，则该图是强连通的。

这两种算法的时间复杂度均为线性。

和普通的深度优先搜索一样，您需要跟踪每个节点的状态：未访问、已访问但仍处于开放状态（在调用栈中），以及已经访问并完成。此外，您还需要存储第一次到达节点时的深度以及从节点可达的最低深度（在完成节点后可以知道）。如果一个节点的最低可达深度等于其自身深度，则该节点为强连通分量的根节点。即使从根节点到达节点的深度不是可能的最小值，这也是有效的。

要仅检查整个图是否为单个强连通分量，请从任何单个节点开始进行深度优先搜索，并在完成后，如果最低可达深度为0且每个节点都已访问，则整个图是强连通的。

- Jonathan Graehl

Answer 3

检查给定图中每个节点是否具有到其他节点和从其他节点的两条路径：

1. 从所有节点进行深度优先搜索（DFS）/广度优先搜索（BFS）：

Tarjan算法 假设每个节点都有一个深度d[i]。最初，根节点具有最小深度。我们对任何邻居j的后序DFS更新d[i] = min(d[j])。实际上，BFS在这里使用减少规则d[i] = min(d[j])也可以正常工作。

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])

如果从u到v有一条转发路径，则d[u]≤d[v]。在SCC中，d[v]≤d[u]≤d[v]，因此，SCC中的所有节点深度相同。要判断一个图是否是SCC，我们检查所有节点是否具有相同的d[i]。

2.从单个节点开始的两个DFS/BFS：

这是Kosaraju算法的简化版本。从根节点开始，我们检查是否可以通过DFS/BFS到达每个节点。然后，反转每条边的方向。我们再次检查是否可以从相同的根节点到达每个节点。请参见C ++代码。

- lxy

Answer 4

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
}

- brock

Answer 5

您可以计算所有对最短路径，并查看是否有任何一条是无穷的。

- Adam Crume

---

可能是这样，但这里肯定有更有效的方法。 - Noldorin

Answer 6

Tarjan算法已经被提到过了。但是我通常发现Kosaraju算法更容易理解，尽管它需要对图进行两次遍历。如果我没记错的话，在CLRS中也有很好的解释。

- MAK

Answer 7

您可以使用基于Kosaraju的DFS算法，该算法对图进行两次DFS遍历：

思路是，如果每个节点都可以从顶点v到达，并且每个节点都可以到达v，则图是强连通的。在算法的第2步中，我们检查是否可以从v到达所有顶点。在第4步中，我们检查是否可以从所有顶点到达v（在反向图中，如果所有顶点都可以从v到达，则所有顶点都可以在原始图中到达v）。

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

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

3）反转所有弧（或查找图的转置或反向）

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

5）从相同的顶点v开始对反向图进行DFS遍历（与步骤2相同）。如果DFS遍历没有访问所有顶点，则返回false。否则返回true。

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

- aman jadon

Answer 8

检查图是否强连通的算法非常简单。但是下面的算法为什么有效呢？

算法：假设有一个顶点为[A，B，C......Z]的图

1. 选择任意一个随机节点，比如说J，并从它开始执行DFS。如果所有节点都可以到达，则继续进行步骤2。

2. 通过转置来反转图的边方向。

3. 再次从节点J运行DFS，并检查是否访问了所有节点。如果是，则该图是强连通的，并返回true。

执行步骤1是有意义的，因为我们必须检查是否可以从该节点到达所有节点。在此之后，下一个逻辑步骤可能是：

i）现在对所有其他节点执行此操作

ii）或尝试从每个其他节点到达节点J。因为一旦到达节点J，您就可以确定由于步骤1，您可以到达每个其他节点。

这就是我们在第2步和第3步中所尝试的。如果在转置图中节点J能够到达所有其他节点，则意味着在原始图中所有其他节点都可以到达J.

- Ishekk ҆

Answer 9

实现这个的一种方法是为图形生成Laplacian矩阵，然后计算特征值，最后计算零的数量。如果存在唯一的零特征值，则该图形是强连接的。

注意：针对有向图创建Laplacian矩阵的方法略有不同。

- Noldorin