算法介绍

实例代码(cpp代码 pascal代码)

算法效率

算法介绍

Tarjan算法是用来求有向图的强连通分量的。求有向图的强连通分量的Tarjan算法是以其发明者Robert Tarjan命名的。Robert Tarjan还发明了求双连通分量的Tarjan算法，以及求最近公共祖先的离线Tarjan算法，在此对Tarjan表示崇高的敬意。

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

定义DFN(u)为节点u搜索的次序编号(时间戳)，Low(u)为u或u的子树能够追溯到的最早的栈中节点的次序号。

当DFN(u)=Low(u)时，以u为根的搜索子树上所有节点是一个强连通分量。

?

实例代码

cpp代码

?tarjan(u)

{

DFN[u]=Low[u]=++Index //为节点u设定次序编号和Low初值

Stack.push(u) // 将节点u压入栈中

foreach (u, v)in E // 枚举每一条边

if(v is not visted) // 如果节点v未被访问过

tarjan(v) //继续向下找

Low[u]= min(Low[u], Low[v])

elseif(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)

}

pascal代码

procedure tarjan(x:longint);

var i,j,k:longint;

begin

inc(h);

dfn[x]:=h;

low[x]:=h; //dfn，low初始化

inc(t);

f[t]:=x; //当前元素入栈

s[x]:=true;

ss[x]:=true; //s，ss标记

fori:=1 to 200 do

ifp[x,i] then // 枚举每一条边

if not s[i] then begin tarjan(i); // 如果节点i未被访问过继续向下找

low[x]:=min(low[x],low[i]);

end

else if ss[i] thenlow[x]:=min(low[x],dfn[i]); // 如果节点i还在栈内

if dfn[x]=low[x] then begin inc(ans); while f[t]<>x do begin ss[f[t]]:=false; dec(t); end; end;

// 如果节点x是强连通分量的根，退栈直到x，记录这个强连通分量的数据

end;

算法效率

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

求有向图的强连通分量还有一个强有力的算法，为Kosaraju算法。Kosaraju是基于对有向图及其逆图两次DFS的方法，其时间复杂度也是O(N+M)。与Trajan算法相比，Kosaraju算法可能会稍微更直观一些。但是Tarjan只用对原图进行一次DFS，不用建立逆图，更简洁。在实际的测试中，Tarjan算法的运行效率也比Kosaraju算法高30%左右。此外，该Tarjan算法与求无向图的双连通分量(割点、桥)的Tarjan算法也有着很深的联系。学习该Tarjan算法，也有助于深入理解求双连通分量的Tarjan算法，两者可以类比、组合理解。