首页 > 代码库 > 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算法
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。