一、背景介绍
强连通分量是有向图中的一个子图，在该子图中，所有的节点都可以沿着某条路径访问其他节点。强连通性是一种非常重要的等价抽象，因为它满足
- 自反性：顶点V和它本身是强连通的
- 对称性：如果顶点V和顶点W是强连通的，那么顶点W和顶点V也是强连通的
- 传递性：如果V和W是强连通的，W和X是强连通的，那么V和X也是强连通的
强连通性可以用来描述一系列属性，如自然界中物种之间的捕食关系，互相捕食的物种可以看作等价的，在自然界能量传递中处于同一位置。
二、Kosaraju算法描述
Kosaraju算法通过以下步骤获得一个有向图的强连通分量。
- 在图G中，计算图G的反向图G‘的深度优先搜索的逆后序排列。反向图是比如原图中有V到W的链接，那么反向图中就有W到V的链接。逆后序排列是指，在对一个图进行深度优先遍历时，先进行子节点的递归，再将本节点加入到一个栈中，最后依次出栈以获得的序列。逆后序排列有一个重要特性，就是如果有W到V的有向链接，那么实际出栈时，W仍然排在V的前面。
- 在G中进行普通的深度优先搜索，但是搜索顺序不是按照正统的( i = 0, i < N )去依次搜索，而是以刚刚获得的逆后序排列的顺序进行搜索。
- 每个以这个逆后序排列中的元素开始的DFS搜索，找到的所有元素，都是同一个强联通分量的元素。
为什么这个算法可以获得强连通分量呢？网上的证明很少，所以下面给出我的逻辑证明。
三、Kosaraju算法证明
我们按照算法描述的步骤往下走：
- 按照算法的结论，假设我们已经获得了一个逆后序排列，我们从中找两个元素，分别是V,W，W先出栈并且通过DFS找到了V。那么，V和W就是同一个联通分量的元素。到底是不是呢？
- 不管是不是，我们至少可以确定对于该有向图G，W有一条链接通往V，我们记作W->V。那么，对于该有向图的反向图G‘，确定有链接V->W。
- 我们开始思考，在什么条件下，我们能够在反向图 G‘ 中获得V...W（即W先出栈）这样一个排列呢？要知道，我们刚刚确定了有链接V->W，所以逆后序排列中，应该是V排在W的前面，W...V这样啊？
- 所以在G‘中，要么是我们之前提到的，在V->W的同时有W->V的链接；要么就是W和V之间没有任何联系，这样V的DFS结束之后，包含W的联通分量的DFS才开始遍历，才能造成W比V先出栈。
- 但是我们已经知道，V和W不是毫无关系的，确定有链接V->W，所以第二个可能不成立，所以必然存在一个W->V的链接，也就是W和V是互相联通的！
- 证明完毕。
四、算法源码
因为代码很长，放在附件里下载。代码是在Idea中编译运行通过的，实现了一个基本的Graph数据结构，在此基础上实现了Kosaraju类，供参考。
源文件下载
Kosaraju算法分析及证明--强连通分量的线性算法
原文：http://www.cnblogs.com/bethunebtj/p/4854946.html
