DFS实现SCC算法的证明

在《算法导论》（第二版）一书的第22.5节中讲到了强连通分支及其实现方法。但对于为什么使用DFS可以实现强连通分支（个人认为）解释的不够清楚，先参照书中的定义给出自己的证明。

深度优先搜索算法得到强连通分支的过程，可以把一个图分解，从而在图的每一个强连通分支上运行算法。这是深度优先算法的一个重要的应用之一。

在证明之前，先重温书上的一些定义：
1. 强连通分支。强连通分支有两个要点：
   1） 强连通分支必须是图G（V, E）中最大的顶点集合；---体现“强”字
   2） 这个顶点集合中任意两个顶点之间都是相互可到达的；---体现“连通”
2. 任何一个图（有向有/无回路图），通过将强连通分支收缩为其顶点，变成一个分支图G(SCC) = (V(SCC), E(SCC))，使得该分支图为一个有向无回路图；
3. 图G和图G的转置拥有相同的强连通分支（这一性质书中并未给出证明）。

深度优先算法求解强连通分支的步骤如下：
1. 在图G上运行深度优先算法，计算每一个节点的结束时间f(vi)；
2. 计算图G的转置Trans(G);
3. 根据f(vi)从大到小的顺序排列每一个节点，按f(vi)从大到小的顺序遍历此序列，在图Trans(G)上运行DFS，将获得一个森林（一个或多个树构成），则构成这个森林的每一棵树都是一个强连通分支；
注：以上f(vi)都是按照第一次在图G上运行DFS计算出来的时间；

问: 如何证明：按照以上算法计算出来的每一棵深度优先树都是一个强连通分支？
解：
先考虑第二次DFS形成的第一棵树。假设其根节点为r_1, 树中其他节点分别为n_1, n_2, n_3, n_x.
由于遍历节点时是从大到小遍历，因此f(r_1) > f(n_i) (i = 1, 2, 3, 4, ... x). 不失一般性，假设（Trans(G)中）r_1连接的第一个节点时n_1，则有： f(r_1) > f(n_1).
考虑：
1） 如果d(r_1) < f(n_1), 则必有d(r_1) < d(n_1). 则有d(r_1) < d(n_1) < f(n_1) < f(r_1). 即在第一次DFS中n_1是r_1的后裔。而在Trans(G)中，r_1连向n_1, 则在G中，n_1连向r_1。综合以上，说明在G中，n_1和r_1是可以相互连通的；
2） 如果d(r_1) > f(n_1), 则必有d(n_1) < f(n_1) < d(r_1) < f(r_1)。即在G中，r_1和n_1不属于同一棵树，且在访问n_1的树的时候，r_1还是白色。有因为在Trans(G)中r_1连向n_1，则在G中，n_1连向r_1，而且在发现n_1时，r_1是白色，根据白色路径定理，r_1应该是n_1的子裔，这与上面所说的r_1和n_1属于不同的树相矛盾，因此这一假设（d(r_1) > f(n_1)）不成立。
由第二条的矛盾也可以看出：通过以上深度优先算法得出的强连通分支内的每个顶点不可能出现相互之间（时间区间）不包括的关系。

此时再推到n_2，假设n_2连向n_1，即r_1通过n_1连向n_2，和上面的证明方法一样。（这里需要注意的是：只能通过r_1和n_2来证明，而无法通过n_1和n_2来证明，因为无法判断f(n_1)和f(n_2)的关系）。
...
这里即证明了以上通过使用两次DFS，可以使得第一颗深度优先树为强连通分支。

现在使用完全归纳法来证明以上深度优先算法获得的每一颗深度优先树都是强连通分支。
假设第k棵树是强连通分支。其根节点为r_k，其他节点为n_1, n_2, n_3, ... n_x，（为记号方便，这里使用了跟上面一样的符号，注意区分）。则在图Trans(G)中：
1） 不可能同时存在这样两条边：其中第一条边从第k棵树连向底k+1棵树，第二条边从第k+1棵树连向第k棵树；---想想显而易见
2） 不可能存在从第k棵树连向第k+1棵树的边；
3） 可能存在从第k+1棵树连向第k棵树（或更前面树）的边；
总结上面几条为：在DFS搜索Trans(G)形成的树中：不可能有从前面的树连向后面的树的边，但可能存在从后面的树连向前面的树的边；
则在第k+1棵树中即便存在连向或者第i棵树（i<=k）的边，该条边也仅仅是交叉边而已；该条边仅构成分支图的边，而无法构成强连通分支的边。因此，可以在第k+1棵树上使用推导第一棵树为SCC时的方法来证明第k+1棵树也为SCC。根据完全归纳法，原命题得证。