客户端基本不用的算法系列：Tarjan 算法的思路

在之前的 《客户端基本不用的算法系列：从 floodfill 到图的连通性》一文中，我们已经了解了在无向图中的割点和桥的定义。

割点：无向连通图中，去掉一个顶点及和它相邻的所有边，图中的连通分量数增加，则该顶点称为割点。 桥（又叫割边）：无向连通中，去掉一条边，图中的连通分量数增加，则这条边，称为桥或者割边。

另外通过自己的思考，我们也知道了：

1. 有割点不一定有桥，有桥一定存在割点；
2. 桥一定是割点依附的边；

例如下图中 C 为割点，但和 C 相连的边都不是桥：

既然我们已经分清了如何判断割点和桥，那么我们要如何在一张图中将它找出来呢。首先想当然的还是想到了暴力法：DFS。

使用 DFS 暴力求解桥

我们继续研读割点的定义，其实我们模拟这个过程，在图中去掉某个点，然后进行 DFS 搜索，如果第二次比第一次连通分量增加，那么这个点就是割点（是不是很直接，DFS 就是这么暴力）。我们来尝试一下这个方法。首先我们先找一个示例图：

得到邻接矩阵：

我们先计算整张图的联通分量，然后再模拟拆每一个点，计算新图的连通分量。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 算法是如何判断割点的。

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，则根节点就是割点。

以上分析我们得到两个结论：

1. 当该点是根节点，只要子节点数目大于 1，它就是割点；
2. 如果不是根节点，只要节点的子节点不到达祖先顶点，它就是割点；

Tarjan 中的一些概念

Tarjan 算法是基于对图的 DFS 算法的优化，每个强连通分量为搜索树中的一棵子树。搜索时，把当前当前搜索树种未处理的节点加入到一个栈，回溯时可以判断栈顶到栈中的节点是否为一个强连通分量。其中，有两个起作用的关键数组我们需要了解一下：

1. DFN[] 数组：数组存储访问顺序，也就是遍历的点会分配一个序号（从小到大），然后序号存在这个数组当中：DFN[u]为节点 u 搜索的次序编号；
2. LOW[] 数组：表示该点能直接或间接到达时间最小的顶点。例如：LOW[u]为节点 u 的子树能够追溯到最早的栈中节点的次序号；
3. stack 存储该连通子图中的所有点。

另外，在 Tarjan 算法中，如果一次 Tarjan 遍历后，DFN[u] = LOW[u]时，以 u 为根的搜索子树上所有节点是一个强连通分量。

好了，我们有了以上的基础就可以开始正式的学习 Tarjan 的三大算法了。下一篇文章开始，我们就一一的讲解三个算法的使用场景，以及如何使用 DFN[] 、LOW[]和 stack 来实现整个 Tarjan 算法。并且你会发现，最后又变成了可以解决问题的模板（套路）? 。但是在这之前，还是建议先建议大家使用暴力的 DFS 方法来实现下寻找割点以及桥的方法，这个也当做这篇文章对应的习题吧~

下期再见。

对应习题

• 使用 DFS 在连通图中，找出割边集（所有的桥）。