有向图的连通性

一、基本概念

强连通：在有向图 \(G\) 中，如果两点 \(u\) , \(v\) 是互相可达的，则称 \(u\) 和 \(v\) 是强连通的。如果 \(G\) 中的任意两个点都是互相可达的，那么 \(G\) 就是强连通图。

强连通分量：如果一个有向图 \(G\) 不是强连通图，那么可以把它分成多个子图，其中每个子图的内部是强连通的，而且这些子图已经扩展到最大，不能与子图外的任一点强连通，像这样的一个“极大强连通”子图是\(G\)的一个强连通分量( \(\text{Strongly Connected Component}\)，\(\text{SCC}\) ).

\(Tarjan\)算法能在一次DFS中吧所有点都按 \(\text{SCC}\) 分开。这并不是不可思议的，它利用了 \(\text{SCC}\) 的特点。

定理：一个 \(\text{SCC}\)，从其中任何一个点出发。都至少有一条路径能绕回到自己。

二、算法实现

在讲解之前，先了解\(low\)和\(num\)操作。

下面是一个例子，下图有三个 \(\text{SCC}\)，也就是\(\{a,b,d,c\}\)、\(\{e\}\)、\(\{f\}\).

图1.a是原图。图1.b是对它做\(DFS\)，每个点左边的数字标记了\(DFS\)访问它的顺序，也就是\(num[]\)值，右边的划线数字是\(low[]\)值，即能返回到的最远的祖先。每个点的\(low[]\)初始值等于\(num[]\)，即连到自己。观察\(c\)的\(low[]\)值是如何更新的：它的初始值是\(6\)，然后有一个回退到\(a\)，所以更新为\(1\)；它的递归祖先\(d\)、\(b\)的\(low[]\)值也跟着更新为\(1\)。\(e\)和\(f\)的\(low[]\)值不能更新。

图1.b是从\(a\)开始\(DFS\)的，\(a\)成为{\(a,b,d,c\)}这个\(SCC\)的祖先.其实，从{\(a,b,d,c\)}中任意一个点开始\(DFS\)，这个点都会成为这个\(SCC\)的祖先。认识到这些，可以帮助我们理解后面的解释：可以用栈分离不同的\(SCC\)。

图1.b中的\(low[]\)值有\(3\)部分，即等于\(1\)的{\(a,b,d,c\)}、等于\(4\)的{\(f\)}、等于\(5\)的{\(e\)}。这就是\(3\)个\(SCC\)。

完成以上步骤，似乎已经就解决了问题。每个点都有了自己的\(low[]\)值，相同\(low[]\)值的点属于一个\(SCC\)。那么只要再对所有点做一个查询，按\(low[]\)值分开就行了，其复杂度是\(O(V)\)。

其实有更好的办法，即在\(DFS\)的同时把点按\(SCC\)（有相同的\(low[]\)值）分开。

以图2为例，其中有3个\(SCC\)，即\(A\)、\(E\)、\(F\)。假设从F中的一个点开始\(DFS\)，\(DFS\)过程可能会中途跳出\(F\)，转入\(A\)或者\(E\)，总之，最后会进入一个\(SCC\)。

假设DFS过程是\(F\)->\(E\)->\(A\)，最后进入\(A\)。
在\(A\)这个\(SCC\)中将完成\(A\)内所有点的\(DFS\)过程，也就是说，最后的几步\(DFS\)会集中在A中的点\(a\)、\(b\)、\(c\)、\(d\)。这几个点会计算得到相同的\(low[]\)值，标记为一个\(SCC\)，这样就好了。
\(DFS\)递归从\(A\)回到\(E\)。并在E中完成\(E\)内部的\(DFS\)过程。
回到\(F\)，在\(F\)内完成递归过程。