分類導(dǎo)航

Kosaraju算法解析: 求解圖的強(qiáng)連通分量

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

1. 定義

連通分量：在無(wú)向圖中，即為連通子圖。

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

強(qiáng)連通分量：有向圖中，盡可能多的若干頂點(diǎn)組成的子圖中，這些頂點(diǎn)都是相互可到達(dá)的，則這些頂點(diǎn)成為一個(gè)強(qiáng)連通分量。