怎么使用Tarjan算法求解強(qiáng)連通分量

本篇內(nèi)容介紹了“怎么使用Tarjan算法求解強(qiáng)連通分量”的有關(guān)知識，在實(shí)際案例的操作過程中，不少人都會(huì)遇到這樣的困境，接下來就讓小編帶領(lǐng)大家學(xué)習(xí)一下如何處理這些情況吧！希望大家仔細(xì)閱讀，能夠?qū)W有所成！

算法框架

我們來思考一個(gè)問題，對于強(qiáng)連通分量分解的算法來說，它的核心原理是什么?

如果你看過我們之前的文章，那么這個(gè)問題對你來說應(yīng)該不難回答。既然是強(qiáng)連通分量，意味著分量當(dāng)中每個(gè)點(diǎn)都可以互相連通。所以我們很容易可以想到，我們可以從一個(gè)點(diǎn)出發(fā)，找到一個(gè)回路讓它再回到起點(diǎn)。這樣途中經(jīng)過的點(diǎn)就都是強(qiáng)連通分量的一部分。

但是這樣會(huì)有一個(gè)問題，就是需要保證強(qiáng)連通分量當(dāng)中的每個(gè)點(diǎn)都被遍歷到，不能有遺漏。針對這個(gè)問題我們也可以想到解法，比如可以用搜索算法去搜索它所有能夠達(dá)到的點(diǎn)和所有的路徑。但是這樣一來，我們又會(huì)遇到另外一個(gè)問題。這個(gè)問題就是強(qiáng)連通分量之間的連通問題。

我們來看個(gè)例子：

在上面這張圖當(dāng)中如果我們從點(diǎn)1出發(fā)，我們可以達(dá)到圖中的每一個(gè)點(diǎn)。但是我們會(huì)發(fā)現(xiàn)1，2，3是一個(gè)強(qiáng)連通分量，4，5，6是另外一個(gè)。當(dāng)我們尋找1所在的強(qiáng)連通分量的時(shí)候，很有可能會(huì)把4，5，6這三個(gè)點(diǎn)也帶進(jìn)來。但問題是它們是自成分量的，并不應(yīng)該算在1的強(qiáng)連通分量當(dāng)中。

我們整理一下上面的分析和思路可以發(fā)現(xiàn)強(qiáng)連通分量分解這個(gè)算法的核心其實(shí)就是解決這兩個(gè)問題，就是完備性問題。完備意味著不能遺漏也不能冗余和錯(cuò)誤，我們想明白核心問題所在之后就很容易搭建起思維框架，接下來我們再來看算法的描述會(huì)容易理解得多。

算法細(xì)節(jié)

Tarjan算法的第一個(gè)機(jī)制是時(shí)間戳，也就是在遍歷的時(shí)候?qū)γ恳粋€(gè)遍歷到的點(diǎn)打上一個(gè)值。這個(gè)值表示這是第幾個(gè)遍歷的元素。

這個(gè)應(yīng)該很好理解，我們只需要維護(hù)一個(gè)全局的變量，在遍歷的時(shí)候去讓它自增就可以了。我們來寫下Python代碼給大家演示一下：

stamp = 0 stamp_dict = {}def dfs(u):     stamp_dict[u] = stamp    stamp += 1     for v in Graph[u]:         dfs(v)

通過時(shí)間戳我們可以知道每個(gè)點(diǎn)被訪問的順序，這個(gè)順序是正向順序。舉個(gè)例子，比如說假設(shè)u和v兩個(gè)點(diǎn)，u的時(shí)間戳比v小。那么它們之間的關(guān)系只有兩種可能，第一種是u能夠連通到v，說明從u到v的鏈路可以走通。第二種是u不能連通到v，這種情況不論反向的從v到u能否連通都不具有討論意義，因?yàn)樗鼈円欢ú荒芑ハ噙B通。

所以我們想要找到連通的通路還需要找到反向的路徑，在Kosaraju算法當(dāng)中我們是通過反向圖來實(shí)現(xiàn)的。在Tarjan當(dāng)中則采取了另外一種方法。因?yàn)槲覀円呀?jīng)知道各個(gè)點(diǎn)的時(shí)間戳了，我們完全可以通過時(shí)間戳來尋找反向的路徑。什么意思呢?其實(shí)很簡單，當(dāng)我們在遍歷u的時(shí)候如果遇到了一個(gè)比u時(shí)間戳更小的v，那么說明就存在一條反向的路徑從u通向v。如果v這時(shí)候還沒有出棧，意味著v是u的上游的話，那么也就說明存在一條路徑從v通向u。這樣就說明了u和v可以互相連通。

既然找到了一對互相連通的u和v，那么我們需要把它們記錄下來。但問題是我們怎么知道記錄到什么時(shí)候?yàn)橹鼓?這個(gè)邊界在哪里?Tarjan算法設(shè)計(jì)了另外一個(gè)巧妙的機(jī)制解決了這個(gè)問題。

這個(gè)機(jī)制就是low機(jī)制，low[u]表示u這個(gè)點(diǎn)能夠連通到的所有的點(diǎn)的時(shí)間戳的最小值。時(shí)間戳越小說明在搜索樹當(dāng)中的位置越高，也可以理解成u能夠連通到的處在搜索樹中最高的點(diǎn)。那么很明顯了，這個(gè)點(diǎn)就是u這個(gè)點(diǎn)所在強(qiáng)連通分量所在搜索樹某一棵子樹的樹根。

這里可能有一點(diǎn)點(diǎn)繞，我們再來看張圖：

圖中節(jié)點(diǎn)所在的序號就是遞歸遍歷的時(shí)間戳，我們可以發(fā)現(xiàn)對于圖上的每個(gè)點(diǎn)來說它們的low值都是1。很明顯1這個(gè)點(diǎn)在搜索樹當(dāng)中是2，3，4這三個(gè)點(diǎn)的祖先。也就是說這一個(gè)強(qiáng)連通分量的遍歷是從1這個(gè)點(diǎn)開始的。當(dāng)1這個(gè)點(diǎn)出棧的時(shí)候，意味著以1位樹根的子樹已經(jīng)遍歷完了，所有可能存在的強(qiáng)連通分量也都已經(jīng)找完了。

這就帶來了另外一個(gè)問題，我們假設(shè)當(dāng)前點(diǎn)是u，我們?nèi)绾沃纔這個(gè)點(diǎn)是否是圖中1這樣的樹根呢?有沒有什么辦法可以標(biāo)記出來呢?

當(dāng)然是有的，這樣的點(diǎn)有一個(gè)特性就是它們的時(shí)間戳等于它們的low。所以我們可以用一個(gè)數(shù)組維護(hù)找到的強(qiáng)連通分量，當(dāng)這些強(qiáng)連通分量能夠遍歷到的樹根出棧的時(shí)候，把數(shù)組清空。

我們把上面的邏輯整理一下就可以寫出代碼來了：

scc = [] stack = [] def tarjan(u):    dfn[u], low[u] = stamp, stamp    stamp += 1  stack.append(u)         for v in Graph[u]:         if not dfn[v]:             tarjan(v)            low[u] = min(low[u], low[v])        elif v in stack:          low[u] = min(low[u], dfn[v])       if dfn[u] == low[u]:         cur = []        # 棧中u之后的元素是一個(gè)完整的強(qiáng)連通分量        while True:             cur.append(stack[-1])             stack.pop()             if cur[-1] == u:                 break         scc.append(cur)

最后，我們來看一下之前講過的經(jīng)典例子：

首先我們從1點(diǎn)開始，一直深搜到6結(jié)束，當(dāng)遍歷到6的時(shí)候，DFN[6]=4，low[6]=4，當(dāng)6出棧時(shí)滿足條件，6獨(dú)立稱為一個(gè)強(qiáng)連通分量。

同理，當(dāng)5退出的時(shí)候也同樣滿足條件，我們得到了第二個(gè)強(qiáng)連通分量。

接著我們回溯到節(jié)點(diǎn)3，節(jié)點(diǎn)3還可以遍歷到節(jié)點(diǎn)4，4又可以連向1。由于1點(diǎn)已經(jīng)在棧中，所以不會(huì)繼續(xù)遞歸1點(diǎn)，只會(huì)更新low[4] =  1，同樣當(dāng)4退出的時(shí)候又會(huì)更新3，使得low[3] = 1。

最后我們返回節(jié)點(diǎn)1，通過節(jié)點(diǎn)1遍歷到節(jié)點(diǎn)2。2能連通的4點(diǎn)已經(jīng)在棧中，并且DFN[4] >  DFN[2]，所以并不會(huì)更新2點(diǎn)。再次回到1點(diǎn)之后，1點(diǎn)沒有其他點(diǎn)可以連通，退出。退出的時(shí)候發(fā)現(xiàn)low[1] =  DFN[1]，此時(shí)棧中剩下的4個(gè)元素全部都是強(qiáng)連通分量。

“怎么使用Tarjan算法求解強(qiáng)連通分量”的內(nèi)容就介紹到這里了，感謝大家的閱讀。如果想了解更多行業(yè)相關(guān)的知識可以關(guān)注億速云網(wǎng)站，小編將為大家輸出更多高質(zhì)量的實(shí)用文章！