給定一個有向圖 G = (V, E) ，對于任意一對頂點 u 和 v，有 u --> v 和 v --> u，亦即，頂點 u 和 v 是互相可達的，則說明該圖 G 是強連通的（Strongly Connected）。如下圖中，任意兩個頂點都是互相可達的。
而對于有向圖，則不能使用 DFS 或 BFS 進行直接周遊來判斷。如下圖中，如果從頂點 0 開始周遊則可判斷是強連通的，而如果從其它頂點開始周遊則無法抵達所有節點。
那麼，該如何判斷有向圖的強連通性呢？
實際上，解決該問題的較好的方式就是使用強連通分支算法（SCC：Strongly Connected Components），可以在 O(V+E) 時間内找到所有的 SCC。如果 SCC 的數量是 1，則說明整個圖是強連通的。
有向圖 G = (V, E) 的一個強連通分支是一個最大的頂點集合 C，C 是 V 的子集，對于 C 中的每一對頂點 u 和 v，有 u --> v 和 v --> u，亦即，頂點 u 和 v 是互相可達的。
初始化設定所有的頂點為未通路的；
從任意頂點 v 開始進行 DFS 周遊，如果周遊結果沒有通路到所有頂點，則說明圖不是強連通的；
置換整個圖（Reverse Graph）；
設定置換後的圖中的所有頂點為未通路過的；
從與步驟 2 中相同的頂點 v 開始做 DFS 周遊，如果周遊沒有通路到所有頂點，則說明圖不是強連通的，否則說明圖是強連通的。
<a></a>
<a href="http://www.geeksforgeeks.org/connectivity-in-a-directed-graph/" target="_blank">Connectivity in a directed graph</a>
<a href="http://www.geeksforgeeks.org/strongly-connected-components/" target="_blank">Strongly Connected Components</a>
<a href="http://www.geeksforgeeks.org/tarjan-algorithm-find-strongly-connected-components/" target="_blank">Tarjan's Algorithm to find Strongly Connected Components</a>
本文轉自匠心十年部落格園部落格，原文連結：http://www.cnblogs.com/gaochundong/p/kosaraju_check_directed_graph_stronly_connected.html，如需轉載請自行聯系原作者