- BC20260153's blog
强连通
-
BC20260153 @ 5 months ago
有向图的 DFS 生成树主要有 4 种边（不一定全部出现）：
- 树边（tree edge）：示意图中以黑色边表示，每次搜索找到一个还没有访问过的结点的时候就形成了一条树边。
- 反祖边（back edge）：示意图中以红色边表示（即
），也被叫做回边，即指向祖先结点的边。 - 横叉边（cross edge）：示意图中以蓝色边表示（即 ），它主要是在搜索的时候遇到了一个已经访问过的结点，但是这个结点 并不是 当前结点的祖先。
- 前向边（forward edge）：示意图中以绿色边表示（即 ），它是在搜索的时候遇到子树中的结点的时候形成的。
我们考虑 DFS 生成树与强连通分量之间的关系。
如果结点 是某个强连通分量在搜索树中遇到的第一个结点，那么这个强连通分量的其余结点肯定是在搜索树中以 为根的子树中。结点 被称为这个强连通分量的根。
反证法：假设有个结点 在该强连通分量中但是不在以 为根的子树中，那么 到 的路径中肯定有一条离开子树的边。但是这样的边只可能是横叉边或者反祖边，然而这两条边都要求指向的结点已经被访问过了，这就和 是第一个访问的结点矛盾了。得证。
在 Tarjan 算法中为每个结点 维护了以下几个变量：
- ：深度优先搜索遍历时结点 被搜索的次序。
- ：在 的子树中能够回溯到的最早的已经在栈中的结点。设以 为根的子树为 。 定义为以下结点的 的最小值： 中的结点；从 通过一条不在搜索树上的边能到达的结点。
一个结点的子树内结点的 dfn 都大于该结点的 dfn。
从根开始的一条路径上的 dfn 严格递增，low 严格非降。
按照深度优先搜索算法搜索的次序对图中所有的结点进行搜索，维护每个结点的 dfn 与 low 变量，且让搜索到的结点入栈。每当找到一个强连通元素，就按照该元素包含结点数目让栈中元素出栈。在搜索过程中，对于结点 和与其相邻的结点 （ 不是 的父节点）考虑 3 种情况：
- 未被访问：继续对 进行深度搜索。在回溯过程中，用 更新 。因为存在从 到 的直接路径，所以 能够回溯到的已经在栈中的结点， 也一定能够回溯到。
- 被访问过，已经在栈中：根据 low 值的定义，用 更新 。
- 被访问过，已不在栈中：说明 已搜索完毕，其所在连通分量已被处理，所以不用对其做操作。
对于一个连通分量图，我们很容易想到，在该连通图中有且仅有一个 使得 。该结点一定是在深度遍历的过程中，该连通分量中第一个被访问过的结点，因为它的 dfn 和 low 值最小，不会被该连通分量中的其他结点所影响。
因此，在回溯的过程中，判定 是否成立，如果成立，则栈中 及其上方的结点构成一个 SCC。
该算法依靠两次简单的 DFS 实现：
第一次 DFS，选取任意顶点作为起点，遍历所有未访问过的顶点，并在回溯之前给顶点编号，也就是后序遍历。
第二次 DFS，对于反向后的图，以标号最大的顶点作为起点开始 DFS。这样遍历到的顶点集合就是一个强连通分量。对于所有未访问过的结点，选取标号最大的，重复上述过程。
两次 DFS 结束后，强连通分量就找出来了，Kosaraju 算法的时间复杂度为 。
Garbow 算法是 Tarjan 算法的另一种实现，Tarjan 算法是用 dfn 和 low 来计算强连通分量的根，Garbow 维护一个节点栈，并用第二个栈来确定何时从第一个栈中弹出属于同一个强连通分量的节点。从节点 开始的 DFS 过程中，当一条路径显示这组节点都属于同一个强连通分量时，只要栈顶节点的访问时间大于根节点 的访问时间，就从第二个栈中弹出这个节点，那么最后只留下根节点 。在这个过程中每一个被弹出的节点都属于同一个强连通分量。
当回溯到某一个节点 时，如果这个节点在第二个栈的顶部，就说明这个节点是强连通分量的起始节点，在这个节点之后搜索到的那些节点都属于同一个强连通分量，于是从第一个栈中弹出那些节点，构成强连通分量。
