Kosaraju算法

Kosaraju算法（也被称为Kosaraju–Sharir算法）是一个在线性时间内寻找一个有向图中的强连通分量的算法。阿尔佛雷德·艾侯，约翰·霍普克洛夫特和杰弗里·乌尔曼（英语：Jeffrey D. Ullman）相信该算法来自S. Rao Kosaraju（英语：S. Rao Kosaraju）于1978年撰写的一篇未发表论文之中。米卡·夏尔（英语：Micha Sharir）也独立发现了该算法并于1981年将其发表。该算法巧妙地利用了一个定理：“一个图的反向图和原图具有一样的强连通分量”。

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

public class KosarajuAlgorithm {    private boolean marked;    private int id;    private int count=-1;    private Stack<Integer> reversePostOrder;    public KosarajuAlgorithm(Digraph G){        //G.V()返回有向图G的边数        marked=new boolean;        id=new int;        //G.reverse()返回的为G的反向图        Digraph G_reverse=G.reverse();        //本遍循环是将G的反向图的逆后序排列存储在reversePostOrder中        for(int i=0;i<G_reverse.V();i++){            if(!marked){                dfs(G_reverse,i);            }        }        count=0;        //按照G的反向图的逆后排序进行深度优先搜索        for(int i:reversePostOrder){            if(!marked){                dfs(G,i);                count++;            }        }    }    //深度优先搜索    public void dfs(Digraph G,int v){        marked=true;        id=count;        for(int i:G.adj(v)){            if(!marked){                dfs(G,i);            }        }        reversePostOrder.push(v);    }}