上海
前面我們講過問題，主要是針對無向圖的，而對于有向圖我們一般求的是強連通分量，常見的三種解決方式分別是Kosaraju算法，Tarjan算法，和Gabow算法。這里我們先介紹使用Kosaraju算法求有向圖的強連通分量問題。
先說一下什么叫強連通分量，在有向圖 G 中，如果兩個頂點 u，v ，有一條從 u 到 v 的有向路徑，同時還有一條從 v 到 u 的有向路徑，則稱這兩個頂點強連通(strongly connected)。
如果有向圖 G 的任意兩個頂點都強連通，稱 G 是一個強連通圖。有向圖的極大強連通子圖，稱為強連通分量（strongly connected component，SCC）。
如下圖所示，相同顏色的屬于同一個強連通分量，因為在相同顏色中任意一個頂點都有到其他頂點（相同顏色）的路徑。可以看到頂點 7 和頂點 6 不在同一個強連通分量，雖然頂點 7 有到頂點 6 的路徑，但頂點 6 沒有到頂點 7 的路徑。
如果我們把圖中所有的強連通分量縮成一個點，就可以得到一張有向無環圖（Directed acyclic graph，DAG），如下所示：
這個圖一定是無環的，如果是有環的，假如藍色和紅色可以構成環，那么藍色和紅色是相互可達的，而同一顏色中的任意兩點也都是兩兩可達的，所以藍色和紅色應該屬于同一個強連通分量，這與事實不符。
所以我們可以得出當有向圖的所有強連通分量都縮成一個點的時候，構成的圖就是有向無環圖。這里我們該怎么求有向圖的強連通分量呢？如下圖所示：
特別聲明：以上內容(如有圖片或視頻亦包括在內)為自媒體平臺“網易號”用戶上傳并發布，本平臺僅提供信息存儲服務。
Notice: The content above (including the pictures and videos if any) is uploaded and posted by a user of NetEase Hao, which is a social media platform and only provides information storage services.
