分類導(dǎo)航

Tarjan-求強連通分量

發(fā)布時間：2017年05月10日作者： IT網(wǎng)絡(luò)文摘 (該文來自筆記，點擊查看原文)

強連通分量：在一個圖的子圖中，任意兩個點相互可達(dá)，也就是存在互通的路徑，那么這個子圖就是強連通分量（或者稱為強連通分支）。如果一個有向圖的任意兩個點相互可達(dá)，那么這個圖就稱為強連通圖。

當(dāng)我們實現(xiàn)基于dfs的Tarjan算法時，我們用D[i]記錄節(jié)點i被訪問的時間（別的博客用dfn[i]），用F[i]記錄節(jié)點i或i的子樹最小可以返回到的節(jié)點j的D[j]（別的博客用low[i]）。

讓我們模擬一下dfs的過程，每個節(jié)點上左邊的是D的值，右邊的是F的值。

大學(xué)生就業(yè)培訓(xùn),高中生培訓(xùn),在職人員轉(zhuǎn)行培訓(xùn),企業(yè)團(tuán)訓(xùn)

首先從節(jié)點1開始往下深搜，每次搜索都更新D值和F值，此時F值是節(jié)點本身。

大學(xué)生就業(yè)培訓(xùn),高中生培訓(xùn),在職人員轉(zhuǎn)行培訓(xùn),企業(yè)團(tuán)訓(xùn)

當(dāng)搜索到節(jié)點4時，已經(jīng)無法繼續(xù)搜索。而此時D值=F值，所以我們可以判定一個強連通分量（在代碼中，需要借助“?！眮韺ふ覐娺B通分量中所有節(jié)點），這個強連通量就是節(jié)點4。

從圖我們也可以看出，節(jié)點4無法到達(dá)其它任意節(jié)點。