Kosaraju算法分析 (CLRS 22.5)

CLRS写的什么鬼东西根本看不懂啊啊啊

Kosaraju是什么

Wiki表示Kosaraju在1978年发明了这个算法但是没把他的论文发表出来,1981年别人独立发现了该算法并发表。

那为什么不发表呢……

Kosaraju的基本方法

  1. 对$G$进行一次深搜
  2. 求$G$的逆$G^T$,并对所有点按照完成时间降序排序
  3. 对$G^T$进行一次深搜
  4. 同一个深度搜索子过程中的所有点都在同一个联通分量里

正确性证明

Kosaraju算法的正确性证明依赖于定理22.14:

$C$和$C’$都是强连通分量,如果存在$(u,v) \in E$, $u \in C$, $v \in C’$,那么最晚完成时间$f(C) > f(C’)$。

有了以上定理,我们就可以用数学归纳法证明第二次DFS所有的子过程中的点都在同一个连通分量里了。

假设已经找到了$k$个强连通分量,
1. $k=0$,显然正确。
2. $k \neq 0$,假设寻找第$k+1$个强连通分量时,最先找到的点是$u$(树根$u \in C$),那么此时$C$中所有的点都是白色,都会变成$u$的后代。同时,根据22.14得到的推论22.15,所有离开$C$的点一定前往已经被搜索过的强连通分量$C’$。所以在此次搜索中,以$u$为根的树中的所有点一定在同一个强连通分量$C$中。