我們來聊聊圖論當中的強連通分量分解的Tarjan算法。
Kosaraju算法一看這個名字很奇怪就可以猜到它也是一個根據人名起的算法，它的發明人是S. Rao Kosaraju，這是一個在圖論當中非常著名的算法，可以用來拆分有向圖當中的強連通分量。
背景知識
這里有兩個關鍵詞，一個是有向圖，另外一個是強連通分量。有向圖是它的使用范圍，我們只能使用在有向圖當中。對于無向圖其實也存在強連通分量這個概念，但由于無向圖的連通性非常強，只需要用一個集合維護就可以知道連通的情況，所以也沒有必要引入一些算法。
有向圖我們都了解，那么什么叫做強連通分量呢？強連通分量的英文是strongly connected components。這是一個很直白的翻譯，要理解它我們首先需要理解強連通的概念。在有向圖當中，如果兩個點之間彼此存在一條路徑相連，那么我們稱這兩個點強連通。那么推廣一下，如果一張圖當中的一個部分中的每兩個點都連通，那么這個部分就稱為強連通分量。
強連通分量一般是一張完整的圖的一個部分，比如下面這張圖當中的{1, 2, 3, 4}節點就可以被看成是一個強連通分量。
其實求解強連通分量的算法并不止一種，除了Kosaraju之外還有大名鼎鼎的Tarjan算法可以用來求解。但相比Tarjan算法，Kosaraju算法更加直觀，更加容易理解。
算法原理
Kosaraju算法的原理非常簡單，簡單到只有三個步驟：
- 我們通過后序遍歷的方式遍歷整個有向圖，并且維護每個點的出棧順序
- 我們將有向圖反向，根據出棧順序從大到小再次遍歷反向圖
- 對于點u來說，在遍歷反向圖時所有能夠到達的v都和u在一個強連通分量當中
怎么樣，是不是很簡單？
下面我們來詳細闡述一下細節，首先后序遍歷和維護出棧順序是一碼事。也就是在遞歸的過程當中當我們遍歷完了u這個節點所有連通的點之后，再把u加入序列。其實也就是u在遞歸出棧的時候才會被加入序列，那么序列當中存儲的也就是每個點的出棧順序。
這里我用一小段代碼演示一下，看完也就明白了。
popped = [] # 存儲出棧節點
def dfs(u):
for v in Graph[u]:
dfs(v)
popped.Append(u)
我們在訪問完了所有的v之后再把u加入序列，這也就是后序遍歷，和二叉樹的后序遍歷是類似的。
反向圖也很好理解，由于我們求解的范圍是有向圖，如果原圖當中存在一條邊從u指向v，那么反向圖當中就會有一條邊從v指向u。也就是把所有的邊都調轉反向。
我們用上面的圖舉個例子，對于原圖來說，它的出棧順序我們用紅色筆標出。
也就是[6, 4, 2, 5, 3, 1]，我們按照出棧順序從大到小排序，也就是將它反序一下，得到[1, 3, 5, 2, 4, 6]。1是第一個，也就是最后一個出棧的，也意味著1是遍歷的起點。
我們將它反向之后可以得到：
我們再次從1出發可以遍歷到2，3， 4，說明{1, 2, 3, 4}是一個強連通分量。
怎么樣，整個過程是不是非常簡單？
我們將這段邏輯用代碼實現，也并不會很復雜。
N = 7
graph, rgraph = [[] for _ in range(N)], [[] for _ in range(N)]
used = [False for _ in range(N)]
popped = []# 建圖def add_edge(u, v): graph[u].append(v)
rgraph[v].append(u)
# 正向遍歷def dfs(u): used[u] = True for v in graph[u]:
if not used[v]:
dfs(v) popped.append(u)
# 反向遍歷def rdfs(u, scc): used[u] = True scc.append(u)
for v in rgraph[u]:
if not used[v]:
rdfs(v, scc) # 建圖，測試數據 def build_graph(): add_edge(1, 3)
add_edge(1, 2)
add_edge(2, 4)
add_edge(3, 4)
add_edge(3, 5)
add_edge(4, 1)
add_edge(4, 6)
add_edge(5, 6)
if __name__ == "__main__":
build_graph() for i in range(1, N):
if not used[i]:
dfs(i) used = [False for _ in range(N)]
# 將第一次dfs出棧順序反向 popped.reverse() for i in popped:
if not used[i]:
scc = [] rdfs(i, scc) print(scc)
思考
算法講完了，代碼也寫了，但是并沒有結束，仍然有一個很大的疑惑沒有解開。算法的原理很簡單，很容易學會，但問題是為什么這樣做就是正確的呢？這其中的原理是什么呢？我們似乎仍然沒有弄得非常清楚。
這里面的原理其實很簡單，我們來思考一下，如果我們在正向dfs的時候，u點出現在了v點的后面，也就是u點后于v點出棧。有兩種可能，一種可能是u點可以連通到v點，說明u是v的上游。還有一種可能是u不能連通到v，說明圖被分割成了多個部分。對于第二種情況我們先不考慮，因為這時候u和v一定不在一個連通分量里。對于第一種情況，u是v的上游，說明u可以連通到v。
這時候，我們將圖反向，如果我們從u還可以訪問到v，那說明了什么？很明顯，說明了在正向圖當中v也有一條路徑連向u，不然反向之后u怎么連通到v呢？所以，u和v顯然是一個強連通分量當中的一個部分。我們再把這個結論推廣，所有u可以訪問到的，第一次遍歷時在它之前出棧的點，都在一個強連通分量當中。
如果你能理解了這一點，那么整個算法對你來說也就豁然開朗了，相信剩下的細節也都不足為慮了。
今天的文章到這里就結束了，如果喜歡本文的話，請來一波素質三連，給我一點支持吧（關注、轉發、點贊）。
- END -
本文始發于公眾號：TechFlow，求個關注
