如何理解Kosaraju演算法？

1樓：柯西洗襪子

推薦閱讀[1]的中3.4節, 思路很清晰, 解釋得非常直觀. 我大概寫一下我的閱後總結:

首先, 你得熟悉有向圖(digraph)的深度優先搜尋(DFS), 前序(preorder), 後序(postorder), 逆後序(reverse postorder), 有向圖的逆(transpose graph);

如果把乙個強連通分量中的所有點濃縮(contract)成乙個點, 那麼原圖G就變成了乙個有向無環圖(DAG);

易證, 乙個DAG至少有乙個源(source)和乙個匯(sink);

如果我們從sink分量中的任一節點開始DFS, 那麼我們就不能到達其他任何連通分量, 而只能遍歷這個sink分量中的所有節點;

我們要是能夠很容易地就找到sink分量中的乙個節點就好了, 可貌似並不是很容易;

但我們可以很容易找到source分量中的乙個點: 後序列表中的最後乙個點(i.e. 逆後序列表中的第乙個點). 注意, 後序列表中的第乙個點並不一定在sink分量中;

不過沒有關係, G的逆(i.e. G')的source不就是G的sink麼? 搞定!

2樓：

1 先把所有的強連通分量縮成一團（最近知道了這個叫做縮點）

2 團與團之間的出入邊不變，所以整個圖就變成了乙個團的有向無環圖

3對這個有向無環圖進行dfs會有乙個dfs樹，第一次dfs處於根節點的團一定是最後完成的，這個時候根節點全是出邊（不然怎麼叫根節點）

4 所以在第二次逆向dfs中，根節點團就是最先訪問的。

5這時根節點團的出邊就變成了入邊。所以根節點團不能到達其他的強連通分量團。

6 所以這時候從根節點dfs就只能訪問到根節點團（根節點所在的強連通分量）的內部的節點，其他的團同理。

3樓：old羅先森

這個演算法理解花了半天時間，理解了以後發現簡單的很，自己寫的一篇部落格，分享給想快速搞懂的小夥伴們~

為什麼Kosaraju演算法是正確的？--帶你完全搞懂有向圖的Kosaraju演算法 - CSDN部落格

4樓：

為了證明s和v強連通，

首先，運用GR圖得到乙個逆後序，該逆後序可以寫成如下形式：

···，s,···，v，···

從該形式我們可以推斷出兩種情況：

1. dfs(s)start->dfs(v)start->dfs(v)end->dfs(s)end（s，v屬於同一連通分量且GR圖中有s->v）

2. dfs(v)start->dfs(v)end->dfs(s)start->dfs(s)end （s，v屬於兩個連通分量）

接著，在G圖中按照「···，s,···，v，···」的逆後序進行深度優先搜尋，若存在s->v，則說明s，v在GR圖中存在v->s的路徑，則反過來說明GR圖中的情況二是不可能出現的。所以「···，s,···，v，···」的逆後序從側面說明了GR圖中s->v。

總結：在G圖和GR圖中都存在s->v，則說明s->v強連通。

補充，在圖G中使用GR的逆後序，我個人認為就是一種資訊的傳遞，即告訴G圖，GR圖中s已經是在v前面的了（s->v），你只要能按照這個順序再來一遍深度優先搜尋並且搜尋出s->v，就可以直接得到s和v強連通的結果。

5樓：豬鼻蛇

核心的思想或許可以總結成兩點：

圈反過來也是圈

把圈反一半過來會得到兩條路徑

你可以認為第一次搜尋之後按倒過來的順序重新搜，就是為了避開上次走過的路徑。如果這次能找到另一條路徑，和上次那條拼起來就是個圈了。