关于Kosaraju算法(求有向图的强连通分量)证明的理解
图1、计算逆排序
图2、Kosaraju算法求强连通分量
图3、书中给出的算法证明
-
在G中的dfs(s)，假设有s可达v且dfs(v)发生在dfs(s)调用过程中，即dfs(s)直接或间接调用了dfs(v)。此时在遍历顺序中，v应该排在s之后。反证法证明：如果v排在s之前，在dfs(s)遍历到v时，由于dfs(v)在之前已执行过，即marked[v]已经为true，所以dfs(s)将不会直接或间接调用dfs(v)。
-
由于在G中某个强连通图中存在一条s->v的路径，所以也应存在一条v->s的路径。即在G(R)中，应存在一条s->v的路径。根据上面第一点，由于v排在s之后，所以G(R)中求reversePost时dfs(v)应该在dfs(s)结束前结束(因为reversePost是在每个dfs遍历结束后将元素入栈的，入栈时该dfs结束，先入栈的节点排在后面，即先进后出)，所以dfs(v)在dfs(s)结束之前结束。
-
由于在G中存在一条路径s->v，所以在G(R)中存在一条路径v->s。因此在dfs(v)发生的时候，dfs(v)将会检查s是否被遍历过，如果未被遍历过则触发dfs(s)。但是如果dfs(v)触发了dfs(s)，则s将排在v之后，与v排在s之后矛盾。由此可知dfs(v)没有触发dfs(s)。
-
由于dfs(v)没有触发dfs(s)，且在dfs(s)结束之前结束。即在dfs(v)发生时，marked[s]已经被标为true了，但是s还未被push到reversePost中。所以在dfs(v)进行时，dfs(s)已发生但还未结束(发生时marked对应下标被标为true,结束时reversePost对应节点入栈)。即dfs(v)发生在dfs(s)的调用过程中。因此dfs(s)肯定直接或间接调用了dfs(v)。即从s存在一条路径到v。即G(R)中存在一条路径s->v。
-
书中对于这个算法，未能很好地解释算法实现的细节，为何reversePost能够求强连通。所以对某些算法，或许确实能证明他们可以达到效果，却很难理解他们为何能实现。