科萨拉朱算法
![本页使用了标题或全文手工转换](http://images.weserv.nl/?url=//upload.wikimedia.org/wikipedia/commons/thumb/c/cd/Zh_conversion_icon_m.svg/35px-Zh_conversion_icon_m.svg.png)
科萨拉朱算法(英語:Kosaraju's algorithm),也被称为科萨拉朱—夏尔算法,是一个在线性时间内寻找一个有向图中的强连通分量的算法。阿尔佛雷德·艾侯,约翰·霍普克洛夫特和杰弗瑞·乌尔曼相信该算法来自S·拉奥·科萨拉朱于1978年撰写的一篇未发表论文之中[1]。米卡·夏尔也独立发现了该算法并于1981年将其发表[2]。该算法巧妙地利用了一个定理:「一个图的反向图和原图具有一样的强连通分量」。
简介
该算法主要用于枚举图中每一个强连通分量内的所有顶点。该算法可由以下四部分组成[3]:
Java代码实现
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[G.V()];
id=new int[G.V()];
//G.reverse()返回的为G的反向图
Digraph G_reverse=G.reverse();
//本遍循环是将G的反向图的逆后序排列存储在reversePostOrder中
for(int i=0;i<G_reverse.V();i++){
if(!marked[i]){
dfs(G_reverse,i);
}
}
count=0;
//按照G的反向图的逆后排序进行深度优先搜索
for(int i:reversePostOrder){
if(!marked[i]){
dfs(G,i);
count++;
}
}
}
//深度优先搜索
public void dfs(Digraph G,int v){
marked[v]=true;
id[v]=count;
for(int i:G.adj(v)){
if(!marked[i]){
dfs(G,i);
}
}
reversePostOrder.push(v);
}
}
复杂度
当图是使用邻接表形式组建的,科萨拉朱算法需要对整张图进行了两次的完整的访问,每次访问与顶点数和边数之和成正比,所以可以在線性时间内访问完成。该算法在实际操作中要比Tarjan算法和基于路径的强连通分量算法要慢,这两种算法都只需要对图进行一次完整的访问。
当图是使用邻接矩阵形式组建的,算法的时间复杂度为。
参考
- ^ Alfred V. Aho, John E. Hopcroft, Jeffrey D. Ullman. Data Structures and Algorithms. Addison-Wesley. 1983 [2016-02-03]. ISBN 978-0201000238. ,p222--p230
- ^ Micha, Sharir. A strong-connectivity algorithm and its applications in data flow analysis. Computers & Mathematics with Applications. 1981, (7): 67–72 [2016-02-03]. (原始内容存档于2019-04-13).
- ^ Robert Sedgewick, Kevin Wayne. 算法. 北京: 人民邮电出版社. 2012年10月 [2016-02-03]. ISBN 978-7-115-29380-0.,p379--p380
文献及链接
- ([//web.archive.org/web/20190413115618/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]]
- Kosaraju's的简要介绍与证明(页面存档备份,存于互联网档案馆)