kosaraju算法是一種用來計算強連通分量相當有效的算法
什麼是強連通分量
什麼是強連通分量？在這之前先定義一個強連通性（strongconnectivity）的概念：有向圖中，如果一個頂點s到t有一條路徑，t到s也有一條路徑，即s與t互相可達，那么我們說s與t是強連通的。那么在有向圖中，由互相強連通的頂點構成的分量，稱作強連通分量。
關於強連通分量的一些預備條件
證明：一，按照有向圖的約定，每個頂點都有到達自身的路徑，即自環，即任意頂點s到s可達，滿足自反性；二，如果s與t是強連通的，則s到t存在路徑，t到s存在路徑，顯然t與s也是強連通的，滿足對稱性；三，如果r與s強連通，s與t強連通，則r與s互相可達，s與t互相可達，顯然r與t也互相可達，滿足傳遞性。因此，強連通關係可導出一個等價類，這就是強連通分量。進一步的利用這結論可以知道，兩個強連通分量之間木有交集（這個結論很重要）。事實上，圖論與離散數學中的關係有非常密切的……關係。在編程求解強連通分量時，通常做法是對頂點進行編號，擁有相同編號的頂點屬於同一個強連通分量。在求解完之後，通過對編號的比較可以迅速判斷兩個頂點是否是強連通的。
kosaraju算法的實現過程
Kosaraju算法過程上並不複雜。要求解一個有向圖的強連通分量，第一步：在該圖的逆圖上運行DFS，將頂點按照後序編號的順序放入一個數組中（顯然，這個過程作用在DAG上得到的就是一個拓撲排序）；第二步：在原圖上，按第一步得出的後序編號的逆序進行DFS。也就是說，在第二次DFS時，每次都挑選當前未訪問的結點中具有最大後序編號的頂點作為DFS樹的樹根。Kosaraju算法的顯著特徵是，第一，引用了有向圖的逆圖；第二，需要對圖進行兩次DFS（一次在逆圖上，一次在原圖上）。而且這個算法依賴於一個事實：一個有向圖的強連通分量與其逆圖是一樣的（即假如頂點任意頂點s與t屬於原圖中的一個強連通分量，那么在逆圖中這兩個頂點必定也屬於同一個強連通分量，這個事實由強連通性的定義可證）。由於算法的時間取決於兩次DFS，因此時間複雜度，對於稀疏圖是O(V+E)，對於稠密圖是O(V²)，可見這是一個線性算法。Kosaraju的結論是，在第二次DFS中，同一棵搜尋樹上的結點屬於一個強連通分量。
算法正確性的證明
假設頂點s與t屬於第二次DFS森林（注意，第二次是在原圖上搜尋）的同一棵樹，r是這棵樹的根結點。那么有以下兩個事實：一，原圖中由r可達s，這蘊含在逆圖中從s到r有一條路徑；二，r在逆圖中的後序編號大於s（r是樹根，因此r的後序編號比樹中所有的其他結點的都大）。現在要證明的是在逆圖中從r到s也是可達的。好，兩個事實結合起來：一，假設逆圖中r到s不可達，且s到r存在路徑，那么這條路徑將使s的後序編號比r大，與事實一矛盾，排除；二，假設逆圖中r到s存在路徑，正是這條r到s的路徑使得r有更大的後序編號，則r與s是強連通的，假設成立（看上去比較勉強，個人認為這應該是一個空證明）。顯然，兩個事實導出一個結論：逆圖中，r與s互相可達。同理，r與t也互相可達，根據傳遞性，第二次DFS森林中同一棵樹中的所有頂點構成一個強連通分量。另一方面，會不會一個強連通分量的所有頂點沒有出現在第二次DFS森林的同一顆樹中呢？答案是：不會。因為根據DFS的性質，如果r與s強連通，那么由r開始的DFS必定能搜到s。證畢。可見Kosaraju的方法能夠找出有向圖的強連通分量，那么為什麼這個方法可行呢？或者如何實現呢？這正是Kosaraju算法最為精妙的地方，關鍵在於第二次DFS選取的順序：在第一次DFS中，將頂點按照後序編號存放，第二次DFS就按照這個順序的逆序進行搜尋，這保證每次選取的根結點（剛才證明中的r結點）都具有未訪問結點中最大的後序編號，則搜尋中拓展的結點的後序編號都比根結點小，這樣也就滿足了事實二。補充：Kosaraju算法雖然是線性的，但是需要兩次DFS，跟另外兩個著名的求解強分量的算法相比，這是一個劣勢。但是Kosaraju算法有個神奇之處在於：計算之後的強分量編號的順序，剛好是該有向圖K(D)（kernelDAG，核心DAG）的一個拓撲排序！因此Kosaraju算法同時提供了一個計算有向圖K(D)拓撲排序的線性算法。這個結果在一些套用中非常重要。
