Kosaraju算法、Tarjan算法分析及证明--强连通分量的线性算法

一、背景介绍

强连通分量是有向图中的一个子图，在该子图中，所有的节点都可以沿着某条路径访问其他节点。强连通性是一种非常重要的等价抽象，因为它满足

• 自反性：顶点V和它本身是强连通的
• 对称性：如果顶点V和顶点W是强连通的，那么顶点W和顶点V也是强连通的
• 传递性：如果V和W是强连通的，W和X是强连通的，那么V和X也是强连通的

强连通性可以用来描述一系列属性，如自然界中物种之间的捕食关系，互相捕食的物种可以看作等价的，在自然界能量传递中处于同一位置。

下图中，子图{1,2,3,4}为一个强连通分量，因为顶点1,2,3,4两两可达。{5},{6}也分别是两个强连通分量。

二、Kosaraju算法描述

Kosaraju算法通过以下步骤获得一个有向图的强连通分量。

• 在图G中，计算图G的反向图G'的深度优先搜索的逆后序排列。反向图是比如原图中有V到W的链接，那么反向图中就有W到V的链接。逆后序排列是指，在对一个图进行深度优先遍历时，先进行子节点的递归，再将本节点加入到一个栈中，最后依次出栈以获得的序列。逆后序排列有一个重要特性，就是如果有W到V的有向链接，那么实际出栈时，W仍然排在V的前面。
• 在G中进行普通的深度优先搜索，但是搜索顺序不是按照正统的( i = 0, i < N )去依次搜索，而是以刚刚获得的逆后序排列的顺序进行搜索。
• 每个以这个逆后序排列中的元素开始的DFS搜索，找到的所有元素，都是同一个强联通分量的元素。

为什么这个算法可以获得强连通分量呢？网上的证明很少，所以下面给出我的逻辑证明。

三、Kosaraju算法证明

我们按照算法描述的步骤往下走：

1. 按照算法的结论，假设我们已经获得了一个逆后序排列，我们从中找两个元素，分别是V,W，W先出栈并且通过DFS找到了V。那么，V和W就是同一个联通分量的元素。到底是不是呢？
2. 不管是不是，我们至少可以确定对于该有向图G，W有一条链接通往V，我们记作W->V。那么，对于该有向图的反向图G'，确定有链接V->W。
3. 我们开始思考，在什么条件下，我们能够在反向图 G' 中获得V...W（即W先出栈）这样一个排列呢？要知道，我们刚刚确定了有链接V->W，所以逆后序排列中，应该是V排在W的前面，W...V这样啊？
4. 所以在G'中，要么是我们之前提到的，在V->W的同时有W->V的链接；要么就是W和V之间没有任何联系，这样V的DFS结束之后，包含W的联通分量的DFS才开始遍历，才能造成W比V先出栈。
5. 但是我们已经知道，V和W不是毫无关系的，确定有链接V->W，所以第二个可能不成立，所以必然存在一个W->V的链接，也就是W和V是互相联通的！
6. 证明完毕。

四、算法源码

 因为代码很长，放在github上了。代码是在Idea中编译运行通过的，实现了一个基本的Graph数据结构，在此基础上实现了Kosaraju类，供参考。

源文件

五、更加迅速的tarjan算法

部分内容转自https://www.byvoid.com/blog/scc-tarjan

1.Tarjan算法

Tarjan算法是基于对图深度优先搜索的算法，每个强连通分量为搜索树中的一棵子树。搜索时，把当前搜索树中未处理的节点加入一个堆栈，回溯时可以判断栈顶到栈中的节点是否为一个强连通分量。

定义DFN(u)为节点u搜索的次序编号(时间戳)，Low(u)为u或u的子树能够追溯到的最早的栈中节点的次序号。由定义可以得出，

Low(u)=Min
{
    DFN(u),
    Low(v),(u,v)为树枝边，u为v的父节点
    DFN(v),(u,v)为指向栈中节点的后向边(非横叉边)
}

当DFN(u)=Low(u)时，以u为根的搜索子树上所有节点是一个强连通分量。

算法伪代码如下

tarjan(u)
{
    DFN[u]=Low[u]=++Index                      // 为节点u设定次序编号和Low初值
    Stack.push(u)                              // 将节点u压入栈中
    for each (u, v) in E                       // 枚举每一条边
        if (v is not visted)               // 如果节点v未被访问过
            tarjan(v)                  // 继续向下找
            Low[u] = min(Low[u], Low[v])
        else if (v in S)                   // 如果节点v还在栈内
            Low[u] = min(Low[u], DFN[v])
    if (DFN[u] == Low[u])                      // 如果节点u是强连通分量的根
        repeat
            v = S.pop                  // 将v退栈，为该强连通分量中一个顶点
            print v
        until (u== v)
}

2.算法的精要之处如下：

• 为每个加入的节点设定序号，使得后搜索到的节点的序号一定高于前面的节点
• 那么，如果后搜索到的节点的子节点里居然有比它本身还要小的节点，则一定出现了环。有环则必定强连通
• 那么，把该节点的标识节点Low(u)设为发现的后向节点的值DFN(V)
• 然后递归程序返回该节点的上级节点u-1，上级节点判断Low(u-1)的值，也把它指向了刚刚找到的后向节点
• 最后，除了后向节点本身，所有环中的节点都指向该后向节点，那么，我们找到了一个强连通分量。

3.算法流程的演示

从节点1开始DFS，把遍历到的节点加入栈中。搜索到节点u=6时，DFN[6]=LOW[6]，找到了一个强连通分量。退栈到u=v为止，{6}为一个强连通分量。

返回节点5，发现DFN[5]=LOW[5]，退栈后{5}为一个强连通分量。

返回节点3，继续搜索到节点4，把4加入堆栈。发现节点4向节点1有后向边，节点1还在栈中，所以LOW[4]=1。节点6已经出栈，(4,6)是横叉边，返回3，(3,4)为树枝边，所以LOW[3]=LOW[4]=1。

继续回到节点1，最后访问节点2。访问边(2,4)，4还在栈中，所以LOW[2]=DFN[4]=5。返回1后，发现DFN[1]=LOW[1]，把栈中节点全部取出，组成一个连通分量{1,3,4,2}。

至此，算法结束。经过该算法，求出了图中全部的三个强连通分量{1,3,4,2},{5},{6}。

可以发现，运行Tarjan算法的过程中，每个顶点都被访问了一次，且只进出了一次堆栈，每条边也只被访问了一次，所以该算法的时间复杂度为O(N+M)。

求有向图的强连通分量还有一个强有力的算法，为Kosaraju算法。Kosaraju是基于对有向图及其逆图两次DFS的方法，其时间复杂度也是O(N+M)。与Trajan算法相比，Kosaraju算法可能会稍微更直观一些。但是Tarjan只用对原图进行一次DFS，不用建立逆图，更简洁。在实际的测试中，Tarjan算法的运行效率也比Kosaraju算法高30%左右。此外，该Tarjan算法与求无向图的双连通分量(割点、桥)的Tarjan算法也有着很深的联系。学习该Tarjan算法，也有助于深入理解求双连通分量的Tarjan算法，两者可以类比、组合理解。