2021-05-12 14:32:11
20行程式碼實現，使用Tarjan演算法求解強連通分量
2020-09-23 10:30:29
今天是演算法資料結構專題的第36篇文章，我們一起來繼續聊聊強連通分量分解的演算法。
在上一篇文章當中我們分享了強連通分量分解的一個經典演算法Kosaraju演算法，它的核心原理是通過將圖翻轉，以及兩次遞迴來實現。今天介紹的演算法名叫Tarjan，同樣是一個很奇怪的名字，奇怪就對了，這也是以人名命名的。和Kosaraju演算法比起來，它除了名字更好記之外，另外一個優點是它只需要一次遞迴，雖然演算法的複雜度是一樣的，但是常數要小一些。它的知名度也更高，在競賽當中經常出現。
先給大家提個醒，相比於Kosaraju演算法，Tarjan演算法更難理解一些。所以如果你看完本文沒有搞明白的話，建議可以閱讀一下上一篇文章。這兩個演算法的效果和複雜度都是一樣的，其實學會一個就可以，沒必要死磕。
演算法框架
我們來思考一個問題，對於強連通分量分解的演算法來說，它的核心原理是什麼？
如果你看過我們之前的文章，那麼這個問題對你來說應該不難回答。既然是強連通分量，意味著分量當中每個點都可以互相連通。所以我們很容易可以想到，我們可以從一個點出發，找到一個迴路讓它再回到起點。這樣途中經過的點就都是強連通分量的一部分。
但是這樣會有一個問題，就是需要保證強連通分量當中的每個點都被遍歷到，不能有遺漏。針對這個問題我們也可以想到解法，比如可以用搜索演算法去搜索它所有能夠達到的點和所有的路徑。但是這樣一來，我們又會遇到另外一個問題。這個問題就是強連通分量之間的連通問題。
我們來看個例子：
相關文章