科薩拉朱演算法

用于寻找有向图上强连通分量的一种算法

科薩拉朱演算法(英語:Kosaraju's algorithm),也被稱為科薩拉朱—夏爾演算法,是一個在線性時間內尋找一個有向圖中的強連通元件的演算法。阿爾佛雷德·艾侯約翰·霍普克洛夫特傑弗瑞·烏爾曼相信該演算法來自S·拉奧·科薩拉朱英語S. Rao Kosaraju於1978年撰寫的一篇未發表論文之中[1]米卡·夏爾英語Micha Sharir也獨立發現了該演算法並於1981年將其發表[2]。該演算法巧妙地利用了一個定理:「一個圖的反向圖和原圖具有一樣的強連通元件」。

簡介

編輯

該演算法主要用於列舉圖中每一個強連通元件內的所有頂點。該演算法可由以下四部分組成[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 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演算法基於路徑的強連通元件演算法英語Path-based strong component algorithm要慢,這兩種演算法都只需要對圖進行一次完整的訪問。

當圖是使用鄰接矩陣形式組建的,演算法的時間複雜度為 

參考

編輯
  1. ^ Alfred V. Aho, John E. Hopcroft, Jeffrey D. Ullman. Data Structures and Algorithms. Addison-Wesley. 1983 [2016-02-03]. 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]. (原始內容存檔於2019-04-13). 
  3. ^ Robert Sedgewick, Kevin Wayne. 算法. 北京: 人民郵電出版社. 2012年10月 [2016-02-03]. ISBN 978-7-115-29380-0. ,p379--p380

文獻及連結

編輯