Kosaraju算法 有向图的强连通分量

有向图的强连通分量即,在有向图G中,如果两个顶点间至少存在一条路径,称两个顶点强连通(strongly connected)。如果有向图G的每两个顶点都强连通,称G是一个强连通图。非强连通图有向图的极大强连通子图,称为强连通分量(strongly connected components)。

采用的算法是Kosaraju算法。

算法原理:对于图G,转置图(同图中的每边的方向相反)具有和原图完全一样的强连通分量。

具体实现:

1.对原图G进行深度优先遍历,记录每个节点的离开时间time[i]。

2.选择具有最晚离开时间的顶点,对反图GT进行遍历,删除能够遍历到的顶点,这些顶点构成一个强连通分量

3.如果还有顶点没有删除,继续步骤2,否则算法结束。

贴一下看到的例图:

原图对图进行DFS

对 逆图进行DFS得强连通分量

主要代码:

}

原文地址:https://www.cnblogs.com/luckycode/p/5255659.html