Java:实现kosarju的SCC算法（附带源码）

m0_61840987

1707人浏览 · 2025-07-24 00:15:00

m0_61840987 · 2025-07-24 00:15:00 发布

Java 实现 Kosaraju 算法识别有向图的强连通分量

一、项目背景详细介绍

在图论中，强连通分量（Strongly Connected Component，SCC）是指有向图中任意两个顶点互相可达的最大顶点子集。对图进行 SCC 分解，可用于：

依赖分析：编译器和任务调度中检测循环依赖；
社交网络挖掘：发现社区和紧密联系的子群；
缩点 DAG 构造：在状态机或流程图中简化结构便于后续拓扑排序。

Kosaraju 算法是一种经典的两次深度优先搜索（DFS）方法：

第一次 DFS（正向）：对每个未访问节点执行 DFS，并在递归完成后将节点压入栈中，形成按完成时间的栈顶序；
图反转：将所有边方向反向，得到逆图；
第二次 DFS（逆向）：依次从栈顶弹出节点，若该节点在逆图中未访问，则以其为起点执行 DFS，所能访问到的所有节点构成一个 SCC。

该算法时间复杂度为 O(n+m)O(n + m)，实现简单直观，适合教学与工程应用。

二、项目需求详细介绍

输入支持：
- 从命令行或文件读取顶点数 n 和边数 m；
- 依次读取有向边 u v 列表；
功能实现：
- 构建正向邻接表 adj；
- 执行第一次 DFS，填充完成顺序栈；
- 构建逆向邻接表 revAdj；
- 执行第二次 DFS，根据栈顺序识别并收集 SCC；
输出要求：
- 按发现顺序输出每个 SCC 的顶点列表；
- 打印 SCC 总数；
其他需求：
- 完整代码集中在一个 Java 类中，注释清晰；
- 支持大规模图（n,m 达到 10^5）时仍能高效执行；
- 输入校验（顶点编号范围、无效格式）。

三、相关技术详细介绍

邻接表存储：
- 使用 List<List<Integer>>adj 和 revAdj；
深度优先搜索（DFS）：
- 递归或显式栈均可；
栈结构：
- Deque<Integer> stack 存放按完成时间排序的顶点；
时间复杂度：
- 构建邻接表和反向图 O(n+m)O(n + m)；
- 两次 DFS 总计 O(n+m)O(n + m)；
- 空间复杂度 O(n+m)O(n + m)。

四、实现思路详细介绍

构建正向邻接表：
- 初始化 adj 长度为 n；
- 读取每条边 (u,v) 并添加 adj.get(u).add(v)；
第一次 DFS 填栈：
- 初始化 boolean[] visited；
- 对每个 u 若未访问则调用 dfs1(u)：
  - 标记 visited[u]=true，遍历 adj.get(u) 中的 v；
  - 对未访问的 v 递归 dfs1(v)；
  - 递归完成后 stack.push(u)；
构建逆向邻接表：
- 初始化 revAdj；
- 遍历正向边 (u->v)，添加 revAdj.get(v).add(u)；
第二次 DFS 收集 SCC：
- 重置 visited；
- 当 stack 不空：
  - u = stack.pop()；
  - 若未访问，则新建列表 component 并调用 dfs2(u, component)：
    - 标记 visited[u]，将 u 加入 component；
    - 遍历 revAdj.get(u) 中的 v 并对未访问 v 递归 dfs2(v, component)；
  - 将 component 添加到 sccs；
输出：
- 打印 sccs.size() 及各 component 列表。

五、完整实现代码

// =========================== 文件：KosarajuSCC.java ===========================

import java.util.*;

public class KosarajuSCC {
    private int n;
    private List<List<Integer>> adj, revAdj;
    private boolean[] visited;
    private Deque<Integer> stack;
    private List<List<Integer>> sccs;

    public KosarajuSCC(int n) {
        this.n = n;
        adj = new ArrayList<>(n);
        revAdj = new ArrayList<>(n);
        for (int i = 0; i < n; i++) {
            adj.add(new ArrayList<>());
            revAdj.add(new ArrayList<>());
        }
        visited = new boolean[n];
        stack = new ArrayDeque<>();
        sccs = new ArrayList<>();
    }

    // 添加有向边 u->v
    public void addEdge(int u, int v) {
        adj.get(u).add(v);
    }

    // 执行 Kosaraju 算法，返回 SCC 列表
    public List<List<Integer>> run() {
        // 1. 第一次 DFS 填栈
        Arrays.fill(visited, false);
        for (int u = 0; u < n; u++) {
            if (!visited[u]) dfs1(u);
        }
        // 2. 构建逆向图
        for (int u = 0; u < n; u++) {
            for (int v : adj.get(u)) revAdj.get(v).add(u);
        }
        // 3. 第二次 DFS 收集 SCC
        Arrays.fill(visited, false);
        while (!stack.isEmpty()) {
            int u = stack.pop();
            if (!visited[u]) {
                List<Integer> component = new ArrayList<>();
                dfs2(u, component);
                sccs.add(component);
            }
        }
        return sccs;
    }

    // 第一次 DFS
    private void dfs1(int u) {
        visited[u] = true;
        for (int v : adj.get(u)) {
            if (!visited[v]) dfs1(v);
        }
        stack.push(u);
    }

    // 第二次 DFS
    private void dfs2(int u, List<Integer> comp) {
        visited[u] = true;
        comp.add(u);
        for (int v : revAdj.get(u)) {
            if (!visited[v]) dfs2(v, comp);
        }
    }

    // 示例主方法
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        System.out.println("请输入顶点数 n 和边数 m：");
        int n = sc.nextInt(), m = sc.nextInt();
        KosarajuSCC kosaraju = new KosarajuSCC(n);
        System.out.println("请输入每条有向边 u v：");
        for (int i = 0; i < m; i++) {
            kosaraju.addEdge(sc.nextInt(), sc.nextInt());
        }
        List<List<Integer>> sccs = kosaraju.run();
        System.out.println("强连通分量数 = " + sccs.size());
        for (int i = 0; i < sccs.size(); i++) {
            System.out.println("SCC " + i + " : " + sccs.get(i));
        }
    }
}

六、代码详细解读（只说明方法作用）

KosarajuSCC(int n)：初始化邻接表、逆向表及辅助结构。
addEdge(int u, int v)：向正向图添加边。
run()：
1. dfs1：第一次 DFS 填充栈。
2. 构建逆向图。
3. dfs2：第二次 DFS 从栈顶顺序弹出节点收集 SCC。
dfs1(int u)：访问 u 并将完成时间推入栈。
dfs2(int u, List<Integer> comp)：在逆向图中收集一个 SCC。
main：示例入口，读取输入并执行算法。