本文共 2284 字，大约阅读时间需要 7 分钟。

有向图中的强连通性是图论中一个重要的概念，它描述了两个顶点之间的相互可达性。两个顶点v和w被称为强连通的，当且仅当它们互为可达，也就是在有向图中既存在一条从v指向w的路径，也存在一条从w指向v的路径。强连通性具有自反性、对称性和传递性，这些性质使其成为一种等价关系。基于这种等价关系，有向图可以划分为多个强连通分量，每个强连通分量是最大的由相互强连通的顶点组成的子集。

强连通分量的划分与无向图中的连通性类似，但有向图中的连通性要求双向的可达性。一个有向图可能包含1到V个强连通分量，其中V是图中的顶点总数。一个强连通图（即每个顶点都可以从任何其他顶点到达）只包含一个强连通分量，而一个有向无环图（DAG）则包含每个顶点一个强连通分量。

Kosaraju算法是一种有效地找出有向图中的强连通分量的资源敏感算法。其核心思想是通过两次深度优先搜索（DFS）来确定强连通分量。第一次DFS运行在原图的反向图上，生成一个顶点的逆后序序列。第二次DFS在原图上按照这个逆后序序列进行处理，每次递归调用处理的顶点都属于同一个强连通分量。

Kosaraju算法的关键性质是其构造函数中的每一次递归调用所标记的顶点都在同一强连通分量中。这一点由该算法的命题所证实，这使得Kosaraju算法成为强连通性分析的经典方法之一。

以下是一个实现Kosaraju算法的Java代码示例：

package section4_2;public class KosarajuSCC {    private boolean[] marked;    private int[] id;    private int count;    public KosarajuSCC(Digraph G) {        marked = new boolean[G.V()];        id = new int[G.V()];        DepthFirstOrder order = new DepthFirstOrder(G.reverse());        for (int s : order.reversePost()) {            if (!marked[s]) {                dfs(G, s);                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 boolean stronglyConnected(int v, int w) {        return id[v] == id[w];    }    public int id(int v) {        return id[v];    }    public int count() {        return count;    }    public static void main(String[] args) {        int[][] data = {            {4, 2},            {2, 3},            {3, 2},            {6, 0},            {0, 1},            {2, 0},            {11, 12},            {12, 9},            {9, 10},            {9, 11},            {8, 9},            {10, 12},            {11, 4},            {4, 3},            {3, 5},            {7, 8},            {8, 7},            {5, 4},            {0, 5},            {6, 4},            {6, 9},            {7, 6}        };        int vn = 13;        int en = 22;        Digraph digraph = new Digraph(vn, en, data);        KosarajuSCC scc = new KosarajuSCC(digraph);        System.out.println(scc.count());        System.out.println(scc.id(1));        System.out.println(scc.id(2));        System.out.println(scc.id(9));        System.out.println(scc.id(6));        System.out.println(scc.id(8));    }}

转载地址：http://aichz.baihongyu.com/