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

Question

我需要检查有向图是否强连接,或者换句话说,是否所有节点都可以到达任何其他节点(不一定是通过直接边缘).

一种方法是在每个节点上运行DFS和BFS,并查看所有其他节点仍然可访问.

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

Answer 1

考虑以下算法.

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遍历.

Answer 2

Tarjan的强连通组件算法(或Gabow的变体)当然就足够了; 如果只有一个强连接组件,那么图形是强连接的.

两者都是线性时间.

与正常深度优先搜索一样,您可以跟踪每个节点的状态:新的,可见但仍然打开(它在调用堆栈中),并且可以看到并完成.此外,您存储深度,当你第一次到达一个节点,而最低的这样的深度是从节点到达(你知道这你完成一个节点之后).如果最低可达深度等于其自身深度,则节点是强连接组件的根.即使您从根到达节点的深度不是最小可能的,这也可以工作.

要检查整个图是否是单个SCC,请从任何单个节点启动dfs,当您完成时,如果最低可达深度为0,并且每个节点都被访问,则整个图强连接.

Answer 3

要检查给定图中每个节点是否都有往返每个其他节点的路径：

\n\n

1. 所有节点的DFS/BFS：

\n\n

Tarjan 的算法假设每个节点都有一个深度d[i]。最初，根的深度最小。d[i] = min(d[j])我们对 的任何邻居j进行后序 DFS 更新i。实际上，BFS 也可以很好地处理这里的归约规则d[i] = min(d[j])。

\n\n

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

\n\n

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

\n\n

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

\n\n

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

\n