科萨拉朱算法（），也被称为科萨拉朱—夏尔算法，是一个在线性时间内寻找一个有向图中的强连通分量的算法。阿尔佛雷德·艾侯，约翰·霍普克洛夫特和杰弗瑞·乌尔曼相信该算法来自于1978年撰写的一篇未发表论文之中。也独立发现了该算法并于1981年将其发表。该算法巧妙地利用了一个定理：「一个图的反向图和原图具有一样的强连通分量」。

简介
该算法主要用于枚举图中每一个强连通分量内的所有顶点。该算法可由以下四部分组成：

对有向图G取逆，得到G的反向图G^R

利用深度优先搜索求出G^R的逆后排序

对G按照上述逆后排序的序列进行深度优先搜索

同一个深度优先搜索递归子程序中访问的所有顶点都在同一个强连通分量内

Java代码实现
public class KosarajuAlgorithm {
private boolean[] marked;
private int[] id;
private int count=-1;
private Stack reversePostOrder;
public KosarajuAlgorithm(Digraph G){
//G.V()返回有向图G的边数
marked=new boolean[G.V()];
id=new int[G.V()];
//G.reverse()返回的为G的反向图
Digraph G_reverse=G.reverse();
//本遍循环是将G的反向图的逆后序排列存储在reversePostOrder中
for(int i=0;i

复杂度
当图是使用邻接表形式组建的，科萨拉朱算法需要对整张图进行了两次的完整的访问，每次访问与顶点数V和边数E之和V+E成正比，所以可以在線性时间O(V+E)内访问完成。该算法在实际操作中要比Tarjan算法和要慢，这两种算法都只需要对图进行一次完整的访问。

当图是使用邻接矩阵形式组建的，算法的时间复杂度为O(V^2)。

参考
文献及链接

• [http://www.sciencedirect.com/science/article/pii/0898122181900080 Micha Sharir.A strong connectivity algorithm and its applications to data flow analysis. Computers and Mathematics with Applications 7(1):67–72, 1981]]

*[http://lcm.csa.iisc.ernet.in/dsa/node171.html Kosaraju's的简要介绍与证明]