1 回答

TA貢獻1820條經(jīng)驗 獲得超9個贊
您應(yīng)該注意到的第一件事是,圖及其反向的強連通分量集是相同的。實際上,該算法實際上是在反轉(zhuǎn)圖中找到了一組強連通分量,而不是原始圖(但沒關(guān)系,因為兩個圖具有相同的 SCC)。
第一次 DFS 執(zhí)行會產(chǎn)生一個以特定順序保存頂點的堆棧,這樣當(dāng)?shù)诙€ DFS 以該順序(在反轉(zhuǎn)圖上)在頂點上執(zhí)行時,它就會正確計算 SCC。因此,運行第一個 DFS 的全部目的是找到圖頂點的排序,該排序服務(wù)于在反向圖上執(zhí)行 DFS 算法?,F(xiàn)在我將解釋堆棧中頂點順序的屬性是什么,以及它如何在反轉(zhuǎn)圖上執(zhí)行 DFS。
那么棧的屬性是什么?想象 S1 和 S2 是圖中的兩個強連通分量,在逆向圖中,S2 可以從 S1 到達。顯然,S1 也無法從 S2 到達,因為如果是這種情況,S1 和 S2 將合并為一個組件。設(shè) x 是 S1 中頂點中的頂部頂點(即,S1 中的所有其他頂點在堆棧中都低于 x)。類似地,讓 y 成為 S2 中頂點中的頂部頂點(同樣,S2 中的所有其他頂點在堆棧中都低于 y)。屬性是y(屬于S2)在堆棧中高于x(屬于S1)。
為什么這個屬性有幫助?當(dāng)我們在逆向圖上執(zhí)行DFS時,我們是按照堆棧順序來做的。特別是,我們在探索 x 之前探索 y。在探索 y 時,我們探索 S2 的每個頂點,由于 S1 的任何頂點都不能從 S2 到達,所以我們在探索 S1 的任何頂點之前探索 S2 的所有頂點。但這適用于任何一對連接的組件,這樣一個組件可以從另一個組件到達。特別是,堆棧頂部的頂點屬于匯組件,在我們完成對匯組件的探索之后,相對于尚未探索的頂點所誘導(dǎo)的圖,頂部頂點再次屬于匯。
因此,該算法正確地計算了逆向圖中的所有強連通分量,如前所述,它們與原始圖中的相同。
添加回答
舉報