Kosaraju算法的拓扑排序解释

• 拓扑排序对于这个算法的理解有很大的帮助。

Kosaraju算法求强连通分量的步骤是：

在正图中进行一次并找出DFS遍历的退出顺序，记录在栈中（栈顶为最后退出）；
在负图中进行第二次，顺序为从栈顶到栈底，此时即可找出各强连通分量。

对这个过程，拓扑排序可以给出一个简单的解释：

• 假设图上已经完成缩点，则可以得到一张有向无环图（DAG），对这张图，可以轻松得到其拓扑序。
• 假设缩点后图上三个点（也即点集），满足拓扑序，则可以证明，无论中所有点在中访问顺序如何，在栈中，一定存在中的点在上方，和同理。
  证明如下：
  如果先访问到中的点，则一定接下来不会访问到中的点，所以中的点都比中后访问到，于是中的所有点在栈中都比中任意点的高。
  如果先访问到中的点，则在访问之前显然会有的点被访问到（譬如说上述点），因此该点在栈中位置比中任意点都高。
• 从而在进行第二次时，拓扑序靠前的点集中一定有点先访问到。因为第二次中所有边反向，所以拓扑序正好颠倒过来，用上面的例子来讲就是在反向图中有，而访问点集中的任意一个点就可以且仅可以访问到当前点集中的所有点（因为反向图将拓扑序颠倒，所以先访问到出度为的点集，也即中的所有点；同样因为反向图将与之间的有向边反向，使得只能访问到中的点）；访问后的标记相当于将中的所有点出列，此时为新的入度为的点。依次下去，就可以找到所有的强连通分量。