定義：
- 高度聚集節(jié)點(diǎn)群的算法妨蛹，稱為強(qiáng)連通分支
- 強(qiáng)連通分支拆讯，定義為圖G的一個(gè)子集C脂男，C中的任意兩個(gè)頂點(diǎn)之間都有路徑來回，或者能夠相連种呐。
- 圖的轉(zhuǎn)置定義：將v→w宰翅，變?yōu)閣→v，轉(zhuǎn)置在強(qiáng)連通數(shù)量與劃分是相同的爽室。
目的應(yīng)用：
找到強(qiáng)連通分支后汁讼，可對(duì)圖進(jìn)行分類簡化。
方法：
- 對(duì)圖G進(jìn)行DFS計(jì)算肮之，得出開始時(shí)間掉缺、結(jié)束時(shí)間
- 對(duì)圖G進(jìn)行轉(zhuǎn)置，將上述圖G的各頂點(diǎn)的結(jié)束時(shí)間進(jìn)行逆向排序戈擒，對(duì)結(jié)束時(shí)間從長到短的各個(gè)頂點(diǎn)眶明，在轉(zhuǎn)置G中調(diào)用DFS算法，得出新的起始時(shí)間與結(jié)束時(shí)間筐高。
- 每一顆DFS算法得出的深度優(yōu)先森林中的樹搜囱，都是一個(gè)強(qiáng)連通分支。
image.png
image.png
image.png
