|
对于无向图，判断图是否是强连通的，可以直接使用深度优先搜索（DFS）或广度优先搜索（BFS），从任意一个顶点出发，如果遍历的结果包含所有的顶点，则说明图是强连通的。 而对于有向图，则不能使用 DFS 或 BFS 进行直接遍历来判断。如下图中，如果从顶点0 开始遍历则可判断是强连通的，而如果从其它顶点开始遍历则无法抵达所有节点。 实际上，解决该问题的较好的方式就是使用强连通分支算法（SCC：Strongly Connected Components），可以在O(V+E)时间内找到所有的 SCC。如果 SCC 的数量是 1，则说明整个图是强连通的。 实现 SCC 的一种算法就是Kosaraju 算法。Kosaraju 算法基于深度优先搜索（DFS），并对图进行两次 DFS 遍历，算法步骤如下： 从任意顶点 v 开始进行 DFS 遍历，如果遍历结果没有访问到所有顶点，则说明图不是强连通的； 从与步骤 2 中相同的顶点 v 开始做 DFS 遍历，如果遍历没有访问到所有顶点，则说明图不是强连通的，否则说明图是强连通的。 Kosaraju 算法的思想就是，如果从顶点 v 可以抵达所有顶点，并且所有顶点都可以抵达 v，则说明图是强连通的。 |
