Kosaraju算法与Topo排序相对应的直观理解

复习SCC（强连通分量）和Topological Sort（拓扑排序）时，感觉Kosaraju算法的处理和Topo排序很像，思考后对其有一定的直观理解，记录一下：

有环图中的DFS

在Kosaraju算法中，首先构建了反向图，并且在反向图上进行DFS。考虑一个DAG图，有这样的结论：在DAG图中进行DFS得到的完成时间序列的逆序天然就是一个拓扑序列。 在这个性质的基础上，可以进一步扩展：即使有向图中有环，通过DFS得到完成时间序列的逆序，记为序列A，对于通过SCC进行缩点后的DAG，仍然满足拓扑序的要求，也就是说，一个SCC如果在缩点后的DAG图中处于另一个SCC缩点的下游，那么下游SCC中的所有点（记为$S_1$）对于上游SCC中的所有点（记为$S_2$），一定会有一个$S_2$中的点，在所有$S_1$中的点之前 。在缩点 DAG 中，如果 $S_2 \to S_1$，那么在对 $S_2$ 进行 DFS 时，它一定会“覆盖”到 $S_1$。$S_2$ 中第一个被 DFS 发现的那个点（我们称之为该分量的入口），必须等待它下方所有的路径（包括整个 $S_1$）全部递归返回后，它才能宣告“完成”。因此，这个“入口点”的完成时间一定晚于 $S_1$ 中所有点的完成时间。在逆序序列 $A$ 中，这个点就一定会排在所有 $S_1$ 点的前面。
因此，最完整的表述是：即使在有环图中进行DFS，其产生的完成时间序列仍满足：上游分量的最大完成时间 > 下游分量的最大完成时间。

反向图上进行DFS的直观意义

根据上面的分析，在反向图中进行DFS并根据其完成时间从早到晚构建L，然后对其进行逆序得到L’。对于L’来说，其顺序可以保证：其第一个元素一定是反向图中的上游分量中的点。 有了这个保证，只需要说明对该点进行某些方式的搜索，使得该点与其能够访问到的所有点即为这一SCC。如果能够说明这个问题，那么只需要对于L’不断递归执行这样的过程，那么必然就能得到所有的SCC。
因此，从直观上来说，反向图上进行DFS的意义在于让我们找到反向图中最上游的分量的一个点。

反向图与正向图间的拓扑镜像

考虑反向图中的“最上游分量中的一个点”，这个点所在的SCC之所以被称为最上游分量，是因为其在反向图中能够通过某个点伸出的单向边访问到另外一个SCC，不会有其他SCC能访问到它，那么在正向图中，这个SCC对应就不能访问到任何其他SCC。 那么在正向图中，对这个SCC中的点进行DFS，就可以得到一个SCC。而这个需要的点也已经在L’中天然给出。至此，可以说明Kosaraju算法的正确性。
从直观上来考虑，反向图中得到的最上游分量也就是“源点(Source)”，在正向图中的镜像就是“汇点(Sink)”，汇点只能在自己的SCC中流动，不可能泄露到其他SCC中，在取出一个汇点后，又会产生新的汇点，这样便可以得到所有的SCC。

题外话：对于SCC的一种理解

SCC非常类似面向对象程序设计中的封装，而有向边就是对这个封装的访问，封装内部的信息可以互相知悉，而信息的传递则是根据规则在有向边中进行传递。对于题目来说，如果有一些信息非常依赖环，那么可以考虑先求SCC。

题外话：图方向与信息传递，DFS与递归

DFS与递归有着紧密的关系，其实现就是个递归过程。同时从信息传递的角度去理解，DFS天生自带的回溯过程就是总结后继中的信息，然后不断向上更新；其向上更新的过程，需要遵守信息依赖所产生的规则。正向图中信息的传递是从前驱不断向后广播，而反向图中的信息传递是从后驱不断向前更新。一个DFS正向向后的过程传递可达性，回溯向前的过程传递子孙中的信息，而回溯需要等正向结束后才进行，因此，如果某些题目直观的思路非常依赖回溯的过程传递子孙信息，那么可以考虑构建反向图，通过反向图中仅需要广播或许就可以完成。