![](https://csdnimg.cn/release/download_crawler_static/80970288/bg5.jpg)
3 s t a c k . append ( s )
4 se en = set ( )
5 se en . add ( s )
6 while len ( s t a c k ) > 0 :
7 # pop 出 l i s t 中 最 后 一 个 元 素 , 先 进 后 出
8 v e r t e x = s t a c k . pop ( )
9 nodes = graph [ v e r t e x ]
10 for w in nodes :
11 i f w not in se en :
12 s t a c k . append (w)
13 se en . add (w)
14 print ( v e r t e x )
1.1.2 Tarjan 算法
Tarjan 算法是基于对图深度优先搜索的算法,每个强连通分量为搜索树中的
一棵子树。搜索时,把当前搜索树中未处理的节点加入一个堆栈,回溯时可以判断
栈顶到栈中的节点是否为一个强连通分量。
4
Kosaraju 和 Tarjan 之间的区别是:Kosaraju 是基于对有向图及其逆图两次
DFS 的方法,其时间复杂度也是 O(N+M)。与 Tarjan 算法相比,Kosaraju 算法可
能会稍微更直观一些。但是 Tarjan 只用对原图进行一次 DFS,不用建立逆图,更
简洁。
在实际的测试中,Tarjan 算法的运行效率也比 Kosaraju 算法高 30% 左右。
5
Targan 官方给出算法步骤有以下两个 array:
6
• DFN[i]:就是图中每个 node,给每个 node 一个 sequence,DFN 就是遍历每
个 node 的顺序并记录。可以理解为时间戳,也可以理解为 depth rst search
node sequence。
• LOW[i]:这个是记录如果遇到环的话,当前的 node 节点 i 可以到达的最小
的 node id 是多少。
• 核心就是 LOW[i] < DFN[i],说明此点在环里。
4
Tarjan 算法详解,https://blog.csdn.net/jeryjeryjery/article/details/52829142,这个很简洁
5
Tarjan:这个算法大神, https://zhuanlan.zhihu.com/p/348703439
6
图的基础算法 (三) – 强连通分量 SCC,https://www.youtube.com/watch?v=qiAvrfMiRqEt=1s
4