强连通分量(方法)

xiaoxiao2021-02-28  81

求强连通分量的方法:

第一种Kosaraju算法:

(1)第一次对图G进行dfs遍历,并在遍历过程中,记录每一个点的退出顺序

如果以1为起点遍历,访问结点的顺序如下:

1 2 3 5 5 3 2 1 4 4 1    结点第二次访问即退出时,那么我们可以得到结点的退出顺序

5 3 2 4 1

(2)倒置这个图,按照退出顺序的逆序对反图进行第二次dfs遍历  1 4 (退出)2 3 5 (退出)

每次遍历得到的那些点属于同一个强连通分量

第二种Tarjan

另一个挺好的讲解

转载请注明原文地址: https://www.6miu.com/read-58925.html

最新回复(0)