一. 基本原理
如圖，圖中包含了3個(gè)強(qiáng)連通分量（簡(jiǎn)稱SCC，下同），從左到右分別設(shè)為, 則可以抽象為下面的圖2，一個(gè)圈代表一個(gè)SCC
注意到，如果把一個(gè)SCC當(dāng)作一個(gè)結(jié)點(diǎn)，則這個(gè)圖為有向無環(huán)圖，即僅存在從到
的有向邊，不存在從
到
的邊，否則
同屬一個(gè)強(qiáng)連通分量
所以我們只需要用DFS遍歷，并使得圖遍歷的順序?yàn)?, 就可以分別遍歷
的所有結(jié)點(diǎn)
回到圖1，設(shè)訪問每個(gè)強(qiáng)聯(lián)通分量時(shí)第一個(gè)訪問的結(jié)點(diǎn)為這個(gè)強(qiáng)連通分量的leader，我們只要找到一個(gè)方法使得DFS訪問的結(jié)點(diǎn)順序?yàn)?img class="math-inline" src="https://math.jianshu.com/math?formula=leader(S_1)%20%5Cto%20leader(S_2)%20%5Cto%20leader(S_3)" alt="leader(S_1) \to leader(S_2) \to leader(S_3)" mathimg="1">即可
則問題轉(zhuǎn)變?yōu)槿绾握业揭粋€(gè)訪問leader的順序，使得被指向的SCC先訪問
按照DFS訪問圖1的時(shí)候有以下性質(zhì)
- 一個(gè)SCC的leader總是最先訪問，并且最后訪問結(jié)束（遍歷完所有后繼結(jié)點(diǎn)）
- 如果有
則
的leader總是先訪問結(jié)束
如果建立一個(gè)棧finishstack，如果結(jié)點(diǎn)訪問結(jié)束，將其push入棧中，則在finishstack 中pop出來的結(jié)點(diǎn)順序我們就稱為后逆序，這個(gè)后逆序滿足先訪問結(jié)束的SCC的leader 順序先于后訪問結(jié)束的SCC的leader。
如果用leader結(jié)點(diǎn)代替相應(yīng)的SCC，那么后逆序就是用DFS訪問leader的順序
并且，有一個(gè)引理
- 對(duì)圖G求逆得到的
和原圖的SCC相同
所以只要利用DFS訪問,得到后逆序，然后再利用DFS按照后逆序訪問圖G，就可以使得G中被指向的SCC先訪問，最終DFS訪問得到的一個(gè)連通分量就是一個(gè)SCC
二. 方法概述
- 對(duì)原圖取反，從任意一個(gè)頂點(diǎn)開始對(duì)反向圖
- 按照
中頂點(diǎn)出棧順序，對(duì)原圖
進(jìn)行DFS遍歷，一次DFS遍歷中訪問的所有頂點(diǎn)都屬于同一強(qiáng)連通分量。
三. 例子
找出圖G中的強(qiáng)連通分量
第一步：求出
第二步：求出后逆序
由A開始并按照字母序進(jìn)行DFS遍歷，并求出
訪問順序?yàn)?A G B C H D I F E
得到的為 C B D H F I G A E
第三步： 按照后逆序訪問原圖G
出棧順序（后逆序）為 E A G I F H D B C
所以按照這個(gè)順序?qū)進(jìn)行DFS遍歷， 訪問的得到的結(jié)果是（一行為一次DFS遍歷得到的連通圖）
訪問 E：{E}
訪問 A：{A B G F I}
訪問 H：{H}
訪問 D：{D}
訪問 C：{C}
所以得到五個(gè)連通圖：{E}, {A B G F I}, {H}, {D}, {C}
四. 偽代碼
- 獲得finishstack后的原圖遍歷
