在之前的 《客户端基本不用的算法系列:从 floodfill 到图的连通性》一文中,我们已经了解了在无向图中的割点和桥的定义。
割点:无向连通图中,去掉一个顶点及和它相邻的所有边,图中的连通分量数增加,则该顶点称为割点。 桥(又叫割边):无向连通中,去掉一条边,图中的连通分量数增加,则这条边,称为桥或者割边。
另外通过自己的思考,我们也知道了:
例如下图中 C 为割点,但和 C 相连的边都不是桥:
既然我们已经分清了如何判断割点和桥,那么我们要如何在一张图中将它找出来呢。首先想当然的还是想到了暴力法:DFS。
我们继续研读割点的定义,其实我们模拟这个过程,在图中去掉某个点,然后进行 DFS 搜索,如果第二次比第一次连通分量增加,那么这个点就是割点(是不是很直接,DFS 就是这么暴力)。我们来尝试一下这个方法。首先我们先找一个示例图:
得到邻接矩阵:
节点 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
---|---|---|---|---|---|---|---|---|
1 | 0 | 1 | 1 | 0 | 1 | 0 | 0 | 0 |
2 | 1 | 0 | 0 | 1 | 0 | 0 | 0 | 0 |
3 | 1 | 0 | 0 | 0 | 1 | 0 | 0 | 0 |
4 | 0 | 1 | 0 | 0 | 0 | 1 | 1 | 0 |
5 | 1 | 0 | 1 | 0 | 0 | 0 | 0 | 0 |
6 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 1 |
7 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 1 |
8 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 0 |
我们先计算整张图的联通分量,然后再模拟拆每一个点,计算新图的连通分量。show me your code!
import copy
g = [
[ 0, 0, 0, 0, 0, 0, 0, 0, 0],
[ 0, 0, 1, 1, 0, 1, 0, 0, 0],
[ 0, 1, 0, 0, 1, 0, 0, 0, 0],
[ 0, 1, 0, 0, 0, 1, 0, 0, 0],
[ 0, 0, 1, 0, 0, 0, 1, 1, 0],
[ 0, 1, 0, 1, 0, 0, 0, 0, 0],
[ 0, 0, 0, 0, 1, 0, 0, 0, 1],
[ 0, 0, 0, 0, 1, 0, 0, 0, 1],
[ 0, 0, 0, 0, 0, 0, 1, 1, 0],
]
def dfs(p: int, graph: list):
for to in range(1, len(graph)):
if graph[p][to] == 1:
graph[p][to] = 0
graph[to][p] = 0
dfs(p=to, graph=graph)
if __name__ == '__main__':
cg, tot_cc = copy.deepcopy(g), 0
for p in range(1, len(cg)):
for to in range(1, len(cg)):
if cg[p][to] == 1:
tot_cc += 1
dfs(p=p, graph=cg)
print("连通分量", tot_cc)
# 模拟拆点
for lp in range(1, len(g)):
cg = copy.deepcopy(g)
# 解除边
for to in range(1, len(g)):
if lp == to or cg[lp][to] == 0:
continue
cg[lp][to] = 0
cg[to][lp] = 0
# 计算联通分量
cc = 0
for p in range(1, len(g)):
for to in range(1, len(g)):
if cg[p][to] == 1:
cc += 1
dfs(p=p, graph=cg)
print(f'拆掉 {lp} 点的联通分量', cc)
连通分量 1
拆掉 1 点的联通分量 2
拆掉 2 点的联通分量 2
拆掉 3 点的联通分量 1
拆掉 4 点的联通分量 2
拆掉 5 点的联通分量 1
拆掉 6 点的联通分量 1
拆掉 7 点的联通分量 1
拆掉 8 点的联通分量 1
使用 DFS 类似于 Floodfill 染色的方式,来对图进行染色计算联通分量,每次在原图上拆点再次进行染色从而暴力的解决了判断割点的问题。但是这样的复杂度是相当高的,在一次 DFS 中再次遍历点边关系,均摊下来接近 O(N^3)
的复杂度,这是相当耗时的。试想当我们有一万个点的复杂图,处理次数在 10^12
左右,估算处理时间在 1w 秒左右,也就是两个半小时多,如此处理时长是我们不能接受的。
由此,我们需要学习一下 Tarjan 算法是如何判断割点的。
下面这两段话建议大家一定要看明白再往下看!!!切记!
假设 DFS 中我们从顶点 U 访问到了顶点 V(此时顶点V还未被访问过),那么我们称顶点 U 为顶点 V 的父顶点,V 为 U 的孩子顶点。在顶点 U 之前被访问过的顶点,我们就称之为 U 的祖先顶点。
如果顶点 U 的所有孩子顶点可以不通过父顶点 U 而访问到 U 的祖先顶点,那么说明此时去掉顶点 U 不影响图的连通性,U 就不是割点。相反,如果顶点 U 至少存在一个孩子顶点,必须通过父顶点 U 才能访问到 U 的祖先顶点,那么去掉顶点 U 后,顶点 U 的祖先顶点和孩子顶点就不连通了,说明 U 是一个割点。
是的,这两段就是 Tarjan 算法求割点的核心思路,我们通过图来继续学习一下:
首先我们要知道,上图中的箭头表示 DFS 访问的顺序(不是有向图)。对于 D 这个节点来说,D 的孩子顶点可以通过连通区域中橙色的边回到 D 的祖先顶点 C(此时 C 已经被访问过了),所以 D 不是割点。
相反的,上图中的连通区域 2,必须通过 C 才能访问,并且其中没有节点可以访问到 C 的祖先顶点 A、B,那么则说明 C 是割点。
另外我们要考虑一个边界情况,就是 DFS 的根节点(一般情况下都是下标为 0 的节点),因为根节点没有祖先顶点。另外,根节点是不是割点也是很好判断,如果我们从根节点出发,一次 DFS 就能访问到所有的节点,那么根节点就不是割点。反之,如果回溯到根节点后,好友未访问的顶点,需要在相邻节点再次 DFS,则根节点就是割点。
以上分析我们得到两个结论:
Tarjan 算法是基于对图的 DFS 算法的优化,每个强连通分量为搜索树中的一棵子树。搜索时,把当前当前搜索树种未处理的节点加入到一个栈,回溯时可以判断栈顶到栈中的节点是否为一个强连通分量。其中,有两个起作用的关键数组我们需要了解一下:
DFN[]
数组:数组存储访问顺序,也就是遍历的点会分配一个序号(从小到大),然后序号存在这个数组当中:DFN[u]
为节点 u 搜索的次序编号;LOW[]
数组:表示该点能直接或间接到达时间最小的顶点。例如:LOW[u]
为节点 u 的子树能够追溯到最早的栈中节点的次序号;stack
存储该连通子图中的所有点。另外,在 Tarjan 算法中,如果一次 Tarjan 遍历后,DFN[u] = LOW[u]
时,以 u 为根的搜索子树上所有节点是一个强连通分量。
好了,我们有了以上的基础就可以开始正式的学习 Tarjan 的三大算法了。下一篇文章开始,我们就一一的讲解三个算法的使用场景,以及如何使用 DFN[]
、LOW[]
和 stack
来实现整个 Tarjan 算法。并且你会发现,最后又变成了可以解决问题的模板(套路)? 。但是在这之前,还是建议先建议大家使用暴力的 DFS 方法来实现下寻找割点以及桥的方法,这个也当做这篇文章对应的习题吧~
下期再见。