在 《Tarjan 算法的思路》中我们已经给出了 Tarjan 算法中的比较重要的几个元素,我们在这里重新复习一下:
DFN[]
数组:数组存储访问顺序,也就是遍历的点会分配一个序号(从小到大),然后序号存在这个数组当中:DFN[u]
为节点 u 搜索的次序编号;LOW[]
数组:表示该点能直接或间接到达时间最小的顶点。例如:LOW[u]
为节点 u 的子树能够追溯到最早的栈中节点的次序号;stack
存储该连通子图中的所有点。下面我们来聊一聊这几个东西要怎么用。
我们先给出一个强连通分量的定义:在有向图 G 中,如果两个顶点 u, v 之间存在一条 u 到 v 的路径,也存在一个 v 到 u 的路径,则称这两个顶点 u, v 是强连通的(strongly connected)。如果有向图 G 的任意两个顶点都强连通,则称 G 是一个强连通图。
非强连通图有向图的极大强连通子图,称为强连通分量(strongly connected components)。
下图中,子图{1,2,3,4}为一个强连通分量,因为顶点1,2,3,4两两可达。{5},{6}也分别是两个强连通分量,总共三个强连通分量。
我们先给出一个演示 Tarjan 算法的经典图,从根结点 1 开始DFS,把遍历到的节点入栈(1-3-5-6)
,当搜索到 u=6
的时候,DFN[6] = LOW[6]
,当 DFN == LOW
的时候,我们认为找到一个强连通分量。然后执行弹栈操作,直到 u == v
为止,{6}
为一个强连通分量。
此时我们在图中标记一下 6 节点,计作 DFN = 4,LOW = 4
。之后回溯到 5 节点,发现 DFN[5] == LOW[5]
,同 6 节点一样继续进行弹栈操作, {5}
为一个强连通分量。
回溯到结点 3,继续 DFS 搜索到结点 4,把 4 进栈。这时发现节点 4 向节点 1 有后向边,节点 1 还在栈中。所以 LOW[4] = 1
。由于节点 6 已经弹栈, 边 (4, 6)
是指向非栈中节点的横叉边,因此不更新 LOW[4]
。回溯返回到结点3,(3, 4)
为树枝边,所以 LOW[3] = LOW[4] = 1
。
横叉边:从某个结点指向搜索树中另一个子树中的某结点的边 树枝边:DFS 时经过的边,即 DFS 搜索树上的边。
回溯到根结点 1,最后 DFS 到点 2。访问边 (2, 4),此时点 4 还在栈中,所以 LOW[2] = DFN[4] = 5
返回 1 后,发现 DFN[1] = LOW[1]
,所以我们就将栈中的点全部取出,组成一个强连通分量 {1, 3, 4, 2}
。
至此,算法结束。我们通过一次 DFS ,求出了图中全部的三个强连通分量 {1, 3, 4, 2}
,{5}
,{6}
。
可以发现,在 Tarjan 算法中,每个顶点都被访问了一次,且只进出一次栈,每条边也只被访问了一次,所以算法时间复杂度为 O(n + m)
。