天天看點

有向圖的強連通算法 -- tarjan算法

(畫圖什麼真辛苦)

強連通分量:

有向圖的強連通算法 -- tarjan算法

在有向圖 G 中,若兩個頂點互相可達,則稱兩個頂點強連通(strongly

connected)。如果有向圖G的每兩個頂點都強連通,稱G是一個強連通圖。非強連通圖有向圖的極大強連通子圖,稱為強連通分量(strongly

connected components)。比如上面這幅圖(

a, b, e ), ( d, c, h ), ( f, g ) 分别為三個 SCC。

tarjan算法僞代碼:

該算法由 Robert

Tarjan 發明,原論文:

時間複雜度是深搜的時間複雜度 O( N

+ E )。

tarjan算法的執行動态圖:

1.建圖,每個頂點有三個域,第一個是頂點名,第二個空格是發現該點的時間戳 DFN ,第三個空格是該點能夠追溯到的最早的棧中節點的次序号

LOW。

有向圖的強連通算法 -- tarjan算法

2. 深搜,比如搜尋路徑為 a --> b --> c --> g --> f, 沿途記下自身的 DFN 和 LOW

有向圖的強連通算法 -- tarjan算法

3.達到 f 點後,f 點隻有一個可達頂點 g, 但 g 不是 f 的後繼頂點,且 g 在棧中,則更新 f 的 LOW 變為 g 的發現時間。

有向圖的強連通算法 -- tarjan算法

4.這時候回到 g 點,但是 f 點還得再棧中,隻有發現時間 DFN 與 LOW 相同的頂點才能從棧中彈出(和壓在上面的節點一起彈出構成SCC)

有向圖的強連通算法 -- tarjan算法

5.這時候 g 點的 DFN == LOW

有向圖的強連通算法 -- tarjan算法

6.于是将 f 和 g 都彈出

有向圖的強連通算法 -- tarjan算法

7.如虛線所示,他們構成了一個SCC

有向圖的強連通算法 -- tarjan算法

8.下面就是一樣的了,( 圖畫的好辛苦 )

有向圖的強連通算法 -- tarjan算法
有向圖的強連通算法 -- tarjan算法

=========================================================================================

有向圖的強連通算法 -- tarjan算法
有向圖的強連通算法 -- tarjan算法

========================================================================================

有向圖的強連通算法 -- tarjan算法
有向圖的強連通算法 -- tarjan算法
有向圖的強連通算法 -- tarjan算法
有向圖的強連通算法 -- tarjan算法

==========================================================================================

有向圖的強連通算法 -- tarjan算法
有向圖的強連通算法 -- tarjan算法
有向圖的強連通算法 -- tarjan算法

python代碼:

運作結果:

有向圖的強連通算法 -- tarjan算法

C++代碼:

繼續閱讀