科薩拉朱算法

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

簡介

該算法主要用於枚舉圖中每一個強連通分量內的所有頂點。該算法可由以下四部分組成：

1. 對有向圖$G$取逆，得到$G$的反向圖$G^{R}$
2. 利用深度優先搜索求出$G^{R}$的逆後排序
3. 對$G$按照上述逆後排序的序列進行深度優先搜索
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);
    }
}

複雜度

當圖是使用鄰接表形式組建的，科薩拉朱算法需要對整張圖進行了兩次的完整的訪問，每次訪問與頂點數$V$和邊數$E$之和$V+E$成正比，所以可以在線性時間$O(V+E)$內訪問完成。該算法在實際操作中要比Tarjan算法和基於路徑的強連通分量算法要慢，這兩種算法都只需要對圖進行一次完整的訪問。

當圖是使用鄰接矩陣形式組建的，算法的時間複雜度為$O(V^{2})$。

文獻及鏈接

• （[//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的簡要介紹與證明（頁面存檔備份，存於網際網路檔案館）