计算机科学

首页 > 计算机科学

Kosaraju算法

2018-08-28 09:37:22     所属分类:图算法

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

目录

  • 1 简介
    • 1.1 Java代码实现
  • 2 复杂度
  • 3 参考
  • 4 文献及链接

简介

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

  1. 对有向图取逆,得到的反向图
  2. 利用深度优先搜索求出的逆后排序
  3. 按照上述逆后排序的序列进行深度优先搜索
  4. 同一个深度优先搜索递归子程序中访问的所有顶点都在同一个强连通分量内

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 booleanG.V();
        id=new intG.V();
        //G.reverse()返回的为G的反向图
        Digraph G_reverse=G.reverse();
        //本遍循环是将G的反向图的逆后序排列存储在reversePostOrder中
        for(int i=0;i<G_reverse.V();i++){
            if(!markedi){
                dfs(G_reverse,i);
            }
        }
        count=0;
        //按照G的反向图的逆后排序进行深度优先搜索
        for(int i:reversePostOrder){
            if(!markedi){
                dfs(G,i);
                count++;
            }
        }
    }
    //深度优先搜索
    public void dfs(Digraph G,int v){
        markedv=true;
        idv=count;
        for(int i:G.adj(v)){
            if(!markedi){
                dfs(G,i);
            }
        }
        reversePostOrder.push(v);
    }
}

复杂度

当图是使用邻接表形式组建的,Kosaraju算法需要对整张图进行了两次的完整的访问,每次访问与顶点数和边数之和成正比,所以可以在线性时间内访问完成。该算法在实际操作中要比Tarjan算法和基于路径的强连通分量算法英语Path-based strong component algorithm要慢,这两种算法都只需要对图进行一次完整的访问。

当图是使用邻接矩阵形式组建的,算法的时间复杂度为

参考

  1. ^ Alfred V. Aho, John E. Hopcroft, Jeffrey D. Ullman. Data Structures and Algorithms. Addison-Wesley. 1983. ISBN 978-0201000238.  ,p222--p230
  2. ^ Micha, Sharir. A strong-connectivity algorithm and its applications in data flow analysis. Computers & Mathematics with Applications. 1981, (7): 67–72 [2016-02-03]. 
  3. ^ Robert Sedgewick, Kevin Wayne. 算法. 北京: 人民邮电出版社. 2012年10月. ISBN 978-7-115-29380-0.  ,p379--p380

文献及链接

  • 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的简要介绍与证明

下一篇:骑士巡逻
相关推荐