分類導(dǎo)航

Kosaraju算法解析: 求解圖的強連通分量

發(fā)布時間：2017年02月25日作者：文章轉(zhuǎn)自網(wǎng)絡(luò)，版權(quán)歸原作者所有，反饋可立刻刪除

1. 定義

連通分量：在無向圖中，即為連通子圖。

上圖中，總共有四個連通分量。頂點A、B、C、D構(gòu)成了一個連通分量，頂點E構(gòu)成了一個連通分量，頂點F，G和H，I分別構(gòu)成了兩個連通分量。

強連通分量：有向圖中，盡可能多的若干頂點組成的子圖中，這些頂點都是相互可到達的，則這些頂點成為一個強連通分量。