tarjan算法

有向图的强连通分量是一个极大强连通子图。一个强连通子图是一个节点集合,使得集合中的任意两个点互相可达。本文介绍有向图强连通分量的tarjan算法,并且提供了理解tarjan算法所需要的前置DFS知识。
直观上来讲,tarjan算法对有向图建立搜索树,每一个连通分量都是该搜索树的一棵子树。tarjan算法由一个dfs构成,在dfs过程中,将访问过的节点压入一个栈中,栈顶到栈中的的某个元素构成一个极大强连通分量。

DFS相关知识补充

相对于先前简单的vis数组,首先要介绍DFS的黑白灰染色法,我们规定当节点未被发现时为白色,被发现后为灰色,在它的所有邻接链表被扫描完毕后为黑色。使用黑白灰染色法能够方便我们进行下面的讨论。
tarjan算法基于DFS,我们从任意一点$p$开始遍历,在DFS的过程中会形成一棵树(或者森林),称为DFS树。假如说我们从点$u$访问到一个尚未被访问的点$v$,那么边$(u, v)$是一条树边,体现在DFS上就是$v$是$u$的儿子。同理,紧接着从$v$继续DFS到另一个未发现的点$w$,那么边$(v, w)$也是一条树边。下面我们回到节点$u$,现在我们发现从$u$居然还有一条直接到$w$的边,这里的边$(u, w)$称为前向边,可惜在DFS时所有的前向边都不会体现在DFS树中,这是因为此时$vis[w]$必然为true,因此$w$是$u$的非儿子的后代。我们考虑刚才的前向边$(u, w)$,此时$u$为灰色,因为它访问的$w$节点还没有返回;$w$为黑色,$v$也是黑色,因为它的dfs已经返回了。下面我们考虑在此之前的一个情况,当$w$还是灰色的时候,它应该已经在$u$之前发现过$(u, w)$这条边了,但是这时候$u$和$w$都是灰色,这种情况就和上面之前看到的前向边不一样了,我们称他为后向边。后向边是一个非常有用的东西,它可以用来发现环和计算下面的强连通分量。我们还需要注意到后向边的一个性质,也就是$u.d < w.d$,这是显然的。除此之外,还有一种横向边,不过所幸我们的DFS中只会出现树边和后向边。

tarjan算法原理

我们容易发现可以把一个强连通分量看成搜索树中的一棵子树。我们在DFS的过程中不断将我们发现的节点加入一个堆栈,这个栈其实也对应这DFS的递归。
算法需要$dfn[u]=1..vertex\_count$记录对节点$u$的访问次序, 对应着算法导论中的属性$u.d$,即该节点从白变灰的时间戳,记录这个次序主要是为了处理后向边。$low[u]$记录节点$u$的最早祖先,它表示$u$或$u$的子树能够追溯到的最早的还在栈中的节点的时间戳,我们在将一个节点由灰标黑时计算该节点对应的$low$值。显然,在遍历前我们要设置初始的$dfn[u]$和$low[u]$等于时间戳$index$。当遍历后仍然是$dfn[u]==low[u]$时,$u$不存在可到达的祖先了,得到极大强连通分量。此时$u$也作为这个子树的根(并查集也有类似的性质)。这时我们考察堆栈,根离栈顶最远,永远在最后被弹出。
$low[u]$在三种情况下更新:

  1. 当存在树边$(u, v)$时,应当尝试用$low[v]$更新$low[u]$。这种情况发生在节点$u$发现一个白色节点$v$的时候,此时首先会递归地调用dfs来计算$v$节点,当$v$节点的遍历完成也就是变黑后,dfs返回到我们在$u$节点的调用处,这时候我们尝试用$low[v]$和$low[u]$之间的较小值更新$low[u]$。因此$low[v]$总是先于$low[u]$被更新,可以通过$dfn[v]$是否为0判断$v$是否被访问过
  2. 当存在后向边$(u, v)$时,当此时$v$还在栈中时,应当尝试用$dfn[v]$更新$low[u]$,这里自环也被认作后向边。注意我们必须要判断在$v$是否在栈中,因为$v$可能已经是个黑色节点了,这时$(u, v)$是一条横向边。
    因此可以得到$low[i]$的过程
    1
    2
    3
    4
    5
    6
    7
    8
    9
    def tarjan(u)
    for each (u ,v) in E
    if (!dfn[v])
    // 注意一定要先进行dfs
    tarjan(v);
    low[u] = min(low[u], low[v])
    else if(v exist in stack)
    low[u] = min(low[u], dfn[v])
    // 否则v属于另一个连通分量已被弹出

下面是整个tarjan算法

1
2
3
4
5
6
7
8
9
10
11
12
13
void tarjan(int u){
dfn[u] = low[u] = ++index;
stack.push(u);
update low[u]
if(dfn[u] == low[u]) // 注意不要把if写在update的for each循环里面
pop stack to u // 注意是u不是dfn[u]
}
int main(){
zero(dfn);
for each u in V
if(!dfn(u))
tarjan(u)
}

可以看到算法对于每个点都访问一次,由dfn(u)!=0保证,同样,对每个边$(u, v)$都访问一次。

割点与桥

求割点和桥是tarjan算法的一个经典应用。

LCA Tarjan

这里的LCA Trajan是一种离线算法,它首先先要进行$O(n)$得到预处理。它的思路是第一次找到两个节点的时候,如果记录了他们的最低单亲节点,那么这个单亲节点就是LCA。