Kosaraju 算法检测有向图的强连通性
浏览数：29 /
时间：2015年06月08日
给定一个有向图 G = (V, E) ，对于任意一对顶点 u 和 v，有 u --> v 和 v --> u，亦即，顶点 u 和 v 是互相可达的，则说明该图 G 是强连通的（Strongly Connected）。如下图中，任意两个顶点都是互相可达的。
对于无向图，判断图是否是强连通的，可以直接使用深度优先搜索（DFS）或广度优先搜索（BFS），从任意一个顶点出发，如果遍历的结果包含所有的顶点，则说明图是强连通的。
而对于有向图，则不能使用 DFS 或 BFS 进行直接遍历来判断。如下图中，如果从顶点 0 开始遍历则可判断是强连通的，而如果从其它顶点开始遍历则无法抵达所有节点。
那么，该如何判断有向图的强连通性呢？
实际上，解决该问题的较好的方式就是使用强连通分支算法（SCC：Strongly Connected Components），可以在 O(V+E) 时间内找到所有的 SCC。如果 SCC 的数量是 1，则说明整个图是强连通的。
有向图 G = (V, E) 的一个强连通分支是一个最大的顶点集合 C，C 是 V 的子集，对于 C 中的每一对顶点 u 和 v，有 u --> v 和 v --> u，亦即，顶点 u 和 v 是互相可达的。
实现 SCC 的一种算法就是 Kosaraju 算法。Kosaraju 算法基于深度优先搜索（DFS），并对图进行两次 DFS 遍历，算法步骤如下：
- 初始化设置所有的顶点为未访问的；
- 从任意顶点 v 开始进行 DFS 遍历，如果遍历结果没有访问到所有顶点，则说明图不是强连通的；
- 置换整个图（Reverse Graph）；
- 设置置换后的图中的所有顶点为未访问过的；
- 从与步骤 2 中相同的顶点 v 开始做 DFS 遍历，如果遍历没有访问到所有顶点，则说明图不是强连通的，否则说明图是强连通的。
郑重声明：本站内容如果来自互联网及其他传播媒体，其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。
