Tarjan

2018王菁芃 · 2018-10-17 20:10:55 · 个人记录

有向图强连通分量的Tarjan算法

一、定义

在有向图 G 中， 如果两个顶点 u,v 间存在一条路径 u 到 v 的路径且也存在一条 v 到 u 的路径，则称这两个顶点 u,v 是强连通的(strongly connected)。如果有向图 G 的每两个顶点都强连通， 称 G 是一个强连通图。 有向非强连通图的极大强连通子图， 称为强连通分量(strongly connected components)。若将有向图中的强连通分量都缩为一个点，则原图会形成一个 DAG（有向无环图）。

极大强连通子图： G 是一个极大强连通子图当且仅当 G 是一个强连通子图且不存在另一个强连通子图 G’使得 G 是 G’的真子集。下图中，子图{1,2,3,4}为一个强连通分量，因为顶点 1,2,3,4 两两可达。{5},{6}也分别是两个强连通分量。

二、Tarjan算法

Tarjan 算法是基于对图深度优先搜索(DFS)的算法， 每个强连通分量为搜索树中的一棵子树（的一部分）。搜索时，把当前搜索树中未处理的结点加入一个栈，回溯时可以判断栈顶 到栈中的结点是否为一个强连通分量。

DFS 过程中遇到的四种边：

• 树枝边：DFS 时经过的边，即 DFS 搜索树上的边
• 前向边：与 DFS 方向一致，从某个结点指向其某个子孙的边
• 后向边：与 DFS 方向相反，从某个结点指向其某个祖先的边
• 横叉边：从某个结点指向搜索树中另一子树中的某结点的边

定义 DFN(u)为结点 u 搜索的次序编号(时间戳)，Low(u)为 u 或 u 的子树（经过最多一条后向边或栈中横叉边）能够回溯到的最早的栈中结点的次序号。

由定义可以得出:

Low(u)=Min
{
    DFN(u),
    Low(v),(u,v)为树枝边，u 为 v 的父结点
    DFN(v),(u,v)为后向边或指向栈中结点的横叉边
}

当结点 u 的搜索过程结束后，若 DFN(u)=Low(u)，则以 u 为根的搜索子树上所有还在栈 中的结点是一个强连通分量。

算法伪代码如下:

tarjan(u)
{
    DFN[u]=Low[u]=++Index // 为结点 u 设定次序编号和 Low 初值
    Stack.push(u) // 将结点 u 压入栈中
    for each (u, v) in E // 枚举每一条边
    if (v is not visted) // 如果结点 v 未被访问过
    tarjan(v) // 继续向下找
    Low[u] = min(Low[u], Low[v])
    else if (v in S) // 如果结点 v 还在栈内
    Low[u] = min(Low[u], DFN[v])
    if (DFN[u] == Low[u]) // 如果结点 u 是强连通分量的根
    repeat
    v = S.pop // 将 v 退栈，为该强连通分量中一个顶点
    print v
    until (u== v)
}

三、算法流程演示

从结点 1 开始 DFS，把遍历到的结点加入栈中(1->3->5->6)。搜索到结点 u=6 时，DFN[6]=LOW[6]，找到了一个强连通分量。退栈到 u=v 为止，{6}为一个强连通分量。

返回结点 5，发现 DFN[5]=LOW[5]，退栈后{5}为一个强连通分量。

返回结点 3，继续搜索到结点 4，把 4 加入栈。发现结点 4 向结点 1 有后向边，结点 1还在栈中，所以 LOW[4]=1。

结点 6 已经出栈，(4,6)是指向非栈中结点的横叉边，因此不更新LOW[4]返回 3，(3,4)为树枝边，所以 LOW[3]=LOW[4]=1。

继续回到结点 1，最后访问结点 2。访问边(2,4)，4 还在栈中，所以 LOW[2]=DFN[4]=5。

返回 1 后，发现 DFN[1]=LOW[1]，把栈中结点全部取出，组成一个连通分量{1,3,4,2}。

至此，算法结束。经过该算法，求出了图中全部的三个强连通分量{1,3,4,2},{5},{6}。

可以发现，运行 Tarjan 算法的过程中，每个顶点都被访问了一次，且只进出了一次栈，每条边也只被访问了一次，所以该算法的时间复杂度为 O(N+M)。