有向图强连通分支:Kosaraju’s algorithm

有向图强连通分支算是个基础算法,不过总是忘记,写下来备忘。

无向图强连通分支非常简单,使用图的遍历算法(DFS或BFS)即可,而有向图的强连通分支计算则要复杂一些,Kosaraju’s algorithm实现了\(O(n+m)\)时间复杂度的有向图强连通分支算法。

算法的核心思想在于:从有向图中任何一个点出发做DFS,必然能从图中“拖”出一个点集,和无向图中不同的是,这个点集不一定构成强连通分支,但是如果我们能通过一个合适的顺序进行DFS(“sink” vertex),则可以依次把每一个强连通分支“拖”出来,得到正确的结果,那么算法的要点则在于如何寻找这个合适的顺序。

继续阅读: