首页 > 代码库 > Tarjan算法

Tarjan算法

 

一种由Robert Tarjan提出的求解有向图强连通分量的线性时间的算法。 

Tarjan算法是基于对图深度优先搜索的算法,每个强连通分量为搜索树中的一棵子树。搜索时,把当前搜索树中未处理的节点加入一个堆栈,回溯时可以判断栈顶到栈中的节点是否为一个强连通分量。 
定义dfn(u)为节点u搜索的次序编号,low(u)为u或u的子树能够追溯到的最早的栈中节点的次序号。 
当dfn(u)=low(u)时,以u为根的搜索子树上所有节点是一个强连通分量。

算法图解: 
技术分享
技术分享
技术分享
技术分享
技术分享
技术分享
技术分享
技术分享
技术分享
技术分享
技术分享
技术分享
技术分享

伪代码:

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])    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
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17

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

 

Tarjan算法