强连通分量算法(Tarjan's Strongly Connected Component Algorithm)
利用深度优先算法找到一个非强连通的有向图中的所有强连通子图。无向图可以被认为是同时具备u->v和v->u的图。
一些概念
-
强连通:在有向图中,任意点u与v之间存在有来回两个方向的通路,类似存在一个环;
-
强连通图:图中任意两点存在强连通;
-
强连通分量:图中存在强连通的子图;
-
DFN(u):定义为第一次访问点u时的时间戳;
-
LOW(u):定义为u或u的子树能够回溯到的最早的栈中节点的DFN(u)。
思路
当dfn[u] = low[u]时,以u为根的子树上所有节点是一个强连通分量。
-
首次访问某点u时,令low[u] = dfn[u] = index(or time)(初始化)
-
每到达一个点u,将其入栈(dfs的内容)
-
遍历所有与点u相连的点v:
-
若v不在栈中(树枝边)即未被访问过,递归方法继续往v后面搜索(如dfs()/tarjan()),最终会得出新的low[v];即low[u]=min(low[u], low[v]);
-
若v在栈内即已被访问,通过比较low[u]和v第一次被访问时的序列号/次数,来更新low[u],即low[u] = min(low[u], dfn[v])。
-
图解(来自史上最清晰的Tarjan算法详解-segementFault)
强连通分量:[{0,1,2,3},{4},{5}]
第一步:从节点0开始
-
首先访问 0 -> 2 -> 4 -> 5并将其加入栈。根据访问顺序标记为1至4。这里也可以从0往1走。
-
对于节点5(栈内第一个元素),没有后续的节点了,检查到dfn[5] = low[5] = 4,所以退栈,得{5}为一个强连通分量。
第二步:返回节点4
-
节点4只有一个子树(节点5,已退栈),因此low[4] = min(low[4], low[5]) = low[4] = 3。
-
节点4后无其他子节点,且low[4] = dfn[4],退栈,得到第二个强连通分量。
第三步:返回节点2,并访问节点3及其子树
-
low[2] = min(low[2], low[4]) = 2,节点4(已出栈)是其中一个子节点, 节点2仍有后续子节点;
-
继续探索节点2的另一个子节点3。节点3入栈,初始化dfn[3] = low[3] = 5;
-
发现节点3有通向节点0的路径,且节点0仍在栈中,有low[3] = min(low[3], dnf[0]) = 1;
-
发现节点3有通向节点5的路径,但5已退栈,无需更新low[3]。
第四步:从节点3返回节点2
-
根据刚刚得到的新low[3]更新low[2] = min(low[2], low[3]) = 1;
-
节点2无其他后续子节点,返回0
第五步:返回节点0,并访问节点1及其子树
-
根据low[2]更新low[0],low[0] = min(low[0], low[2]) = 1;
-
发现节点1,dfn[1] = low[1] = 6;
-
发现后续节点3且3还在栈内,low[1] = min(low[1], dfn[3]) = 5
第六步:返回节点0
- dfn[0] = low[0] = 1, 退栈至0,得
伪代码
void tarjan(int u) {
++index;
dfn[u] = low[u] =index; // 节点u的初始值
stack.push(u); // 入栈
for (auto& e : edges[u]) { // 遍历与u相连的点
if (!visited[e]) { // 若e未被访问过
tarjan(e); // 继续向下找其子节点
low[u] = min(low[u], low[v]);
}
else if (e is in stack) { // 若e被访问过且还在栈内
low[u] = min(low[u], dfn[e]);
}
}
if (dfn[u] == low[u]) { // 遍历完所有子节点后,检查是否相等
while (!stack.empty()) { // 循环退栈并打印
v = stack.pop();
print v;
}
}
}