检查有向图是否强连通的算法
-
07-07-2019 - |
题
我需要检查有向图是否是 强关联, ,或者换句话说,如果任何其他节点都可以到达所有节点(不一定通过直接边)。
实现此目的的一种方法是在每个节点上运行 DFS 和 BFS,并查看所有其他节点是否仍可访问。
有更好的方法吗?
解决方案
Tarjan's 强关联组件算法(或 Gabow的变体)当然就足够了;如果只有一个强连接组件,则图形连接很强。
两者都是线性时间。
与正常深度优先搜索一样,您可以跟踪每个节点的状态:新节点,已查看但仍处于打开状态(它位于调用堆栈中),并且已查看并已完成。此外,您可以在第一次到达节点时存储深度,以及从节点可以访问的最低深度(在完成节点后就知道了这一点)。如果最低可达深度等于其自身深度,则节点是强连接组件的根。即使您从根到达节点的深度不是最小可能的深度,这也可以工作。
要检查整个图是否是单个SCC,请从任何单个节点启动dfs,当您完成时,如果最低可达深度为0,并且每个节点都被访问过,那么整个图是强烈联系。
其他提示
考虑以下算法。
从随机顶点开始
v
图表的G
, ,并运行DFS(G, v)
.如果
DFS(G, v)
无法到达图中的所有其他顶点G
, ,那么有一些顶点u
, ,这样就没有从v
到u
, , 因此G
是 不强连接.如果它确实到达每个顶点,则存在一条有向路径
v
到图中的每个其他顶点G
.
反转有向图中所有边的方向
G
.再次运行
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)。