Kosaraju算法详解（Java实现强连通分量查找指南）

Kosaraju算法的核心思想

Kosaraju算法基于一个关键观察：如果我们对原图进行一次深度优先搜索（DFS），记录每个节点完成访问的顺序；然后在图的转置（即所有边反向）上，按照这个完成顺序的逆序再次进行DFS，每次DFS遍历到的所有节点就构成一个强连通分量。

整个过程分为两步：

1. 第一次DFS：遍历原图，将完成访问的节点按顺序压入栈中。
2. 第二次DFS：在转置图上，从栈顶开始依次弹出节点并进行DFS，每次DFS访问到的所有节点组成一个SCC。

Java实现Kosaraju算法

下面是一个完整的Java代码示例，包含图的构建、转置、两次DFS以及输出所有强连通分量。

import java.util.*;public class KosarajuAlgorithm {    private int V; // 顶点数量    private List<List<Integer>> adj; // 邻接表表示原图    public KosarajuAlgorithm(int V) {        this.V = V;        adj = new ArrayList<>(V);        for (int i = 0; i < V; i++) {            adj.add(new ArrayList<>());        }    }    // 添加有向边    public void addEdge(int u, int v) {        adj.get(u).add(v);    }    // 第一次DFS：填充完成栈    private void dfsFillOrder(int v, boolean[] visited, Stack<Integer> stack) {        visited[v] = true;        for (int neighbor : adj.get(v)) {            if (!visited[neighbor]) {                dfsFillOrder(neighbor, visited, stack);            }        }        stack.push(v);    }    // 获取图的转置    private KosarajuAlgorithm getTranspose() {        KosarajuAlgorithm gT = new KosarajuAlgorithm(V);        for (int v = 0; v < V; v++) {            for (int neighbor : adj.get(v)) {                gT.addEdge(neighbor, v); // 反向边            }        }        return gT;    }    // 第二次DFS：打印强连通分量    private void dfs(int v, boolean[] visited) {        visited[v] = true;        System.out.print(v + " ");        for (int neighbor : adj.get(v)) {            if (!visited[neighbor]) {                dfs(neighbor, visited);            }        }    }    // 主函数：执行Kosaraju算法    public void printSCCs() {        Stack<Integer> stack = new Stack<>();        boolean[] visited = new boolean[V];        // 第一步：对原图进行DFS，填充栈        for (int i = 0; i < V; i++) {            if (!visited[i]) {                dfsFillOrder(i, visited, stack);            }        }        // 第二步：获取转置图        KosarajuAlgorithm gT = getTranspose();        // 重置访问数组        Arrays.fill(visited, false);        // 第三步：按栈顺序在转置图上DFS        System.out.println("强连通分量如下：");        while (!stack.isEmpty()) {            int v = stack.pop();            if (!visited[v]) {                gT.dfs(v, visited);                System.out.println(); // 换行表示一个SCC结束            }        }    }    // 测试示例    public static void main(String[] args) {        KosarajuAlgorithm g = new KosarajuAlgorithm(5);        g.addEdge(1, 0);        g.addEdge(0, 2);        g.addEdge(2, 1);        g.addEdge(0, 3);        g.addEdge(3, 4);        g.printSCCs();        // 输出应为：        // 0 2 1         // 3         // 4     }}

代码说明

- KosarajuAlgorithm 类使用邻接表存储图结构。
- getTranspose() 方法创建图的转置。
- dfsFillOrder() 在第一次DFS中将完成访问的节点压入栈。
- printSCCs() 是主逻辑，执行两次DFS并输出所有强连通分量。

时间复杂度分析

Kosaraju算法需要两次DFS遍历，每次遍历的时间复杂度为 O(V + E)，其中 V 是顶点数，E 是边数。因此总时间复杂度为 O(V + E)，非常高效。

应用场景

Kosaraju算法广泛应用于社交网络分析、网页排名（如PageRank预处理）、编译器优化、依赖关系检测等领域。掌握该算法有助于你深入理解Java图算法和有向图SCC的实际应用。

希望这篇关于Kosaraju算法的教程能帮助你轻松入门图论中的强连通分量问题！动手试试代码，加深理解吧！