算法 - 强连通分量 Kosaraju 算法

Kosaraju 算法，也称为 Kosaraju-Sharir 算法：在线性时间内找到有向图的强连通分量。

强连通分量

如果两个顶点 v 和 w 是相互可达的，则称为它们为强连通的。强连通性将所有顶点分为一些平等的部分，每个部分都是由相互均为强连通的顶点的最大子集组成的；我们称这些最大子集为强连通分量。
强连通分量是基于顶点而不是边的，可以认为 V 个顶点的有向图，可能含有 1 ~ V 个强连通分量。一个强连通图，只含有一个强连通分量；一个有向无环图则含有 V 个强连通分量。

强连通分量，必定存在环中。

算法定义

强连通分量的 Kosaraju 算法，使用深度优先 DFS 实现：

• 在给定的有向图 G 中，计算反向图的顶点逆后序排序
• 按照上一步逆后序中顶点的顺序，在 G 中按照深度优先搜索访问未被标记的顶点
• 所有在同一个递归 DFS 调用中被访问到的顶点都在同一个强连通分量中

这里逆后序排序，不是拓扑排序，虽然算法类似，但是拓扑排序针对的是有向无环图，DFS 中会判断是否存在环，检测到环直接退出；而逆后序不检测环，会遍历所有顶点。

动画演示

动画演示和标准的 Kosaraju 算法有点不一样：它是先 DFS 遍历顶点得到逆后序排序，然后再将有向图置为反向图，按照逆后序排序取出顶点，深度优先搜索反向图。结果和 Kosaraju 算法一致。

算法实现

算法解析：

• marked[] 数组
  记录当前顶点是否被访问过。
• count
  记录有多少个强连通分量。
• id[] 数组
  记录当前顶点属于第几个强连通分量。
• G.reverse()
  有向图 G 的反向图：即将所有边的指向全部反过来。
• ReversePostSort.getSort
  使用深度优先搜索获取顶点的逆后序排序。

// Kosaraju-Sharir 强连通分量算法
public class KosarajuSharirSCC {
    private boolean[] marked;
    private int[] id;
    private int count;
    
    public KosarajuSharirSCC(Digraph G) {
        marked = new boolean[G.V()];
        id = new int[G.V()];

        ReversePostSort reverse = new ReversePostSort(G.reverse());
        for (int v : reverse.getSort()) {
            if (!marked[v]) {
                dfs(G, v);
                count++;
            }
        }
    }
    
    private void dfs(Digraph G, int v) { 
        marked[v] = true;
        id[v] = count;
        for (int w : G.adj(v)) {
            if (!marked[w]){
                dfs(G, w);
            }
        }
    }
}

// 深度优先搜索，得到顶点的逆后序排序
public class ReversePostSort{
    private boolean[] marked;
    private Stack<Integer> reversePostOrder;
    
    public ReversePostSort(Digraph G) {
        reversePostOrder = new Stack<Integer>();
        marked = new boolean[G.V()];
        
        for (int v = 0; v < G.V(); v++)
            if (!marked[v]) dfs(G, v);
    }
    
    private void dfs(Digraph G, int v) {
        marked[v] = true;
        for (int w : G.adj(v)) {
            if (!marked[w]) {
                dfs(G, w);
            }
        }
        // 递归后顶点入栈
        reversePostOrder.push(v);
    }
    
    // 获取有向无环图的拓扑排序
    public Iterable<Integer> getSort(){
        return reversePostOrder;
    }
}

小结

• 时间复杂度
  时间复杂度为 O(V+E) 。

参考文档

• 《算法：第四版》 第 4 章
• 强连通分量-Kosaraju算法动画
• 强连通分支算法–Kosaraju算法、Tarjan算法和Gabow算法
• 求解强连通分量算法之—Kosaraju算法