Connectivity Component
Def
SCC
Tarjan
如果结点 u 是某个强连通分量在搜索树中遇到的第一个结点,那么这个强连通分量的其余结点肯定是在搜索树中以 u 为根的子树中。结点 u 被称为这个强连通分量的根。
反证法:假设有个结点 v 在该强连通分量中但是不在以 u 为根的子树中,那么 u 到 v 的路径中肯定有一条离开子树的边。但是这样的边只可能是横叉边或者反祖边,然而这两条边都要求指向的结点已经被访问过了,这就和 u 是第一个访问的结点矛盾了。得证。
Details
在 Tarjan 算法中为每个结点 u 维护了以下几个变量:
深度优先搜索遍历时结点 u 被搜索的次序。
在 u 的子树中能够回溯到的最早的已经在栈中的结点。设以 u 为根的子树为 Subtree_u
。 low_u
定义为以下结点的 dfn
的最小值: Subtree_u
中的结点;从 Subtree_u
通过一条不在搜索树上的边能到达的结点。
对于一个连通分量图,我们很容易想到,在该连通图中有且仅有一个 u 使得
。该结点一定是在深度遍历的过程中,该连通分量中第一个被访问过的结点,因为它的 dfn
和 low
值最小,不会被该连通分量中的其他结点所影响。
Kosaraju
该算法依靠两次简单的 DFS 实现:
第一次 DFS,选取任意顶点作为起点,遍历所有未访问过的顶点,并在回溯之前给顶点编号,也就是后序遍历。
第二次 DFS,对于反向后的图 ,以标号最大的顶点 (实现为stack顶层)作为起点开始 DFS。这样遍历到的顶点集合就是一个强连通分量。对于所有未访问过的结点,选取标号最大的,重复上述过程。
两次 DFS 结束后,强连通分量就找出来了,Kosaraju 算法的时间复杂度为 O(n+m)。
Garbow
Garbow 算法是 Tarjan 算法的另一种实现,Tarjan 算法是用 dfn 和 low 来计算强连通分量的根,Garbow 维护一个节点栈,并用第二个栈来确定何时从 第一个栈 中弹出属于同一个强连通分量的节点。
从节点 w 开始的 DFS 过程中,当一条路径显示这组节点都属于同一个强连通分量时,只要栈顶节点的访问时间大于根节点 w 的访问时间,就从第二个栈中弹出这个节点,那么最后只留下根节点 w。在这个过程中每一个被弹出的节点都属于同一个强连通分量。
当回溯到某一个节点 w 时,如果这个节点在第二个栈的顶部,就说明这个节点是强连通分量的起始节点,在这个节点之后搜索到的那些节点都属于同一个强连通分量,于是从第一个栈中弹出那些节点,构成强连通分量。