每日算法 — 使用java实现强连通分量：Tarjan算法与有向图缩点

引言：有向图中的”孤岛”

在现实世界中，许多关系天然具有方向性：网页之间的超链接、社交媒体的关注关系、程序模块的依赖调用。将这些关系抽象为有向图后，一个基础却深刻的问题是：图中是否存在彼此可达的”紧密团体”？

强连通分量（Strongly Connected Component, SCC） 正是描述这种结构的数学工具。在有向图中，若任意两个顶点互相可达，则它们属于同一个强连通分量。将每个 SCC 收缩为一个”超级节点”，原图便转化为一张有向无环图（DAG）——这一操作被称为缩点，是许多高级图论算法的基石。

本文将用 Java 完整实现 Tarjan 算法 求解强连通分量，讲解 DFS 树中的 dfn/low 双时间戳机制，并展示缩点后如何在 DAG 上进行动态规划求解最长路径。

核心概念：dfn 与 low

Tarjan 算法的精髓在于对 DFS 搜索树的精细刻画。我们为每个节点维护两个时间戳：

• dfn[u]：节点 u 在 DFS 中的访问次序（发现时间）。
• low[u]：从 u 出发，经过零条或多条树边和至多一条回边（指向祖先的横叉边）能到达的最小 dfn 值。

当 dfn[u] == low[u] 时，说明 u 是一个 SCC 的”根”——从 u 出发的所有后代都无法通过回边跳到 u 的祖先。此时，将栈中从 u 往后的所有节点弹出，即构成一个完整的强连通分量。

Tarjan 算法流程

1. 初始化全局时间计数器 timestamp = 0，空栈 stack。
2. 对每个未访问节点启动 DFS：
3. 标记 dfn[u] = low[u] = ++timestamp，u 入栈。
4. 遍历 u 的每个邻接点 v：
   • 若 v 未访问：递归 DFS(v)，回溯后 low[u] = min(low[u], low[v])。
   • 若 v 已访问且在栈中：low[u] = min(low[u], dfn[v])。
5. 若 dfn[u] == low[u]：不断弹栈直到 u 被弹出，弹出的所有节点构成一个 SCC。

缩点：从有向图到 DAG

求得所有 SCC 后，缩点的核心步骤为：

1. 为每个 SCC 分配一个唯一编号 compId。
2. 遍历原图的每条边 (u, v)：
3. 若 compId[u] != compId[v]，则在缩点后的 DAG 中添加边 (compId[u], compId[v])。
4. 去除重边后，得到的图必为 DAG（反证：若存在环，则环上所有节点本应属于同一 SCC）。

缩点后的 DAG 失去了所有环的信息，但保留了节点之间的拓扑依赖关系，使得原本在有向环上无法处理的动态规划问题变得可行。

Java 完整实现

import java.util.*;

/**
 * 强连通分量（SCC）与缩点完整实现
 * 使用 Tarjan 算法，时间复杂度 O(V + E)
 */
public class StronglyConnectedComponents {

    private final int n;                  // 节点数（0-based）
    private final List<Integer>[] graph;  // 邻接表

    private int timestamp;                // DFS 时间戳
    private final int[] dfn;              // 发现时间
    private final int[] low;              // 能到达的最小 dfn
    private final boolean[] inStack;      // 是否在栈中
    private final Deque<Integer> stack;   // 手动栈

    private int sccCount;                 // SCC 数量
    private final int[] compId;           // 每个节点所属 SCC 编号

    public StronglyConnectedComponents(int n) {
        this.n = n;
        this.graph = new ArrayList[n];
        for (int i = 0; i < n; i++) {
            graph[i] = new ArrayList<>();
        }
        this.dfn = new int[n];
        this.low = new int[n];
        this.inStack = new boolean[n];
        this.stack = new ArrayDeque<>();
        this.compId = new int[n];
        Arrays.fill(dfn, -1); // -1 表示未访问
    }

    /** 添加有向边 */
    public void addEdge(int u, int v) {
        graph[u].add(v);
    }

    /** 执行 Tarjan 算法，计算所有 SCC */
    public void tarjan() {
        for (int i = 0; i < n; i++) {
            if (dfn[i] == -1) {
                dfs(i);
            }
        }
    }

    private void dfs(int u) {
        dfn[u] = low[u] = ++timestamp;
        stack.push(u);
        inStack[u] = true;

        for (int v : graph[u]) {
            if (dfn[v] == -1) {
                // 树边：递归访问
                dfs(v);
                low[u] = Math.min(low[u], low[v]);
            } else if (inStack[v]) {
                // 回边（指向栈中祖先）
                low[u] = Math.min(low[u], dfn[v]);
            }
            // 已访问且不在栈中：属于其他已完成的 SCC，忽略
        }

        // 若 u 是 SCC 的根，则弹栈收集整个 SCC
        if (dfn[u] == low[u]) {
            int v;
            do {
                v = stack.pop();
                inStack[v] = false;
                compId[v] = sccCount;
            } while (v != u);
            sccCount++;
        }
    }

    /** 获取节点 u 所属 SCC 编号 */
    public int getCompId(int u) {
        return compId[u];
    }

    /** 获取 SCC 总数 */
    public int getSccCount() {
        return sccCount;
    }

    /** 缩点：构建 DAG 的邻接表（去重边） */
    public List<Integer>[] condense() {
        @SuppressWarnings("unchecked")
        List<Integer>[] dag = new ArrayList[sccCount];
        for (int i = 0; i < sccCount; i++) {
            dag[i] = new ArrayList<>();
        }

        for (int u = 0; u < n; u++) {
            for (int v : graph[u]) {
                if (compId[u] != compId[v]) {
                    dag[compId[u]].add(compId[v]);
                }
            }
        }

        // 去重边
        for (int i = 0; i < sccCount; i++) {
            Set<Integer> set = new HashSet<>(dag[i]);
            dag[i] = new ArrayList<>(set);
        }
        return dag;
    }

    /** 获取每个 SCC 包含的原始节点列表 */
    public List<List<Integer>> getComponents() {
        List<List<Integer>> comps = new ArrayList<>();
        for (int i = 0; i < sccCount; i++) {
            comps.add(new ArrayList<>());
        }
        for (int i = 0; i < n; i++) {
            comps.get(compId[i]).add(i);
        }
        return comps;
    }
}

应用：缩点后 DAG 的最长路径

缩点后得到的 DAG 天然支持拓扑排序。以下示例展示如何在缩点后的 DAG 上求解最长路径（可用于关键路径分析、依赖链长度计算等场景）。

/**
 * 在缩点后的 DAG 上求最长路径（以节点数为单位）
 * 结合拓扑排序与动态规划
 */
public class DAGLongestPath {

    /**
     * @param dag    缩点后的 DAG 邻接表
     * @param sccSize 每个 SCC 的节点数量（路径权重）
     * @return 每个 SCC 为终点的最长路径长度
     */
    public static int[] longestPathInDAG(List<Integer>[] dag, int[] sccSize) {
        int m = dag.length;
        int[] inDegree = new int[m];
        for (int u = 0; u < m; u++) {
            for (int v : dag[u]) {
                inDegree[v]++;
            }
        }

        // Kahn 算法拓扑排序
        Deque<Integer> queue = new ArrayDeque<>();
        for (int i = 0; i < m; i++) {
            if (inDegree[i] == 0) {
                queue.offer(i);
            }
        }

        int[] dp = new int[m]; // dp[i] = 以 i 为终点的最长路径（含 i 自身节点数）
        for (int i = 0; i < m; i++) {
            dp[i] = sccSize[i];
        }

        int processed = 0;
        while (!queue.isEmpty()) {
            int u = queue.poll();
            processed++;
            for (int v : dag[u]) {
                if (dp[u] + sccSize[v] > dp[v]) {
                    dp[v] = dp[u] + sccSize[v];
                }
                inDegree[v]--;
                if (inDegree[v] == 0) {
                    queue.offer(v);
                }
            }
        }

        if (processed != m) {
            throw new IllegalStateException("图中存在环，不是 DAG");
        }
        return dp;
    }
}

完整测试与演示

public class SCCDemo {
    public static void main(String[] args) {
        // 构建测试图：6 个节点，包含两个 SCC
        // SCC1: {0, 1, 2}   SCC2: {3, 4}   孤立点: {5}
        // 边: 0->1, 1->2, 2->0, 1->3, 3->4, 4->3, 3->5
        StronglyConnectedComponents scc = new StronglyConnectedComponents(6);
        scc.addEdge(0, 1);
        scc.addEdge(1, 2);
        scc.addEdge(2, 0);
        scc.addEdge(1, 3);
        scc.addEdge(3, 4);
        scc.addEdge(4, 3);
        scc.addEdge(3, 5);

        scc.tarjan();

        System.out.println("SCC 数量: " + scc.getSccCount());
        System.out.println("各 SCC 包含节点:");
        List<List<Integer>> comps = scc.getComponents();
        for (int i = 0; i < comps.size(); i++) {
            System.out.println("  分量 " + i + ": " + comps.get(i));
        }

        System.out.println("\n节点所属 SCC 编号:");
        for (int i = 0; i < 6; i++) {
            System.out.println("  节点 " + i + " -> SCC " + scc.getCompId(i));
        }

        // 缩点
        List<Integer>[] dag = scc.condense();
        System.out.println("\n缩点后 DAG 的边:");
        for (int u = 0; u < dag.length; u++) {
            System.out.println("  SCC " + u + " -> " + dag[u]);
        }

        // 计算最长路径
        int[] sccSize = new int[scc.getSccCount()];
        for (List<Integer> comp : comps) {
            sccSize[scc.getCompId(comp.get(0))] = comp.size();
        }
        int[] longest = DAGLongestPath.longestPathInDAG(dag, sccSize);
        System.out.println("\n各 SCC 为终点的最长路径长度:");
        for (int i = 0; i < longest.length; i++) {
            System.out.println("  SCC " + i + ": " + longest[i] + " 个节点");
        }
    }
}

运行结果：

SCC 数量: 3
各 SCC 包含节点:
  分量 0: [0, 1, 2]
  分量 1: [3, 4]
  分量 2: [5]
节点所属 SCC 编号:
  节点 0 -> SCC 0
  节点 1 -> SCC 0
  节点 2 -> SCC 0
  节点 3 -> SCC 1
  节点 4 -> SCC 1
  节点 5 -> SCC 2
缩点后 DAG 的边:
  SCC 0 -> [1]
  SCC 1 -> [2]
  SCC 2 -> []
各 SCC 为终点的最长路径长度:
  SCC 0: 3 个节点
  SCC 1: 5 个节点
  SCC 2: 6 个节点

复杂度分析

Tarjan 算法是求解 SCC 的线性算法，在实际应用中比基于 DFS 序的 Kosaraju 算法更节省一次遍历，且只需维护一个栈，常数更小。

总结

本文从有向图的强连通性出发，用 Java 完整实现了 Tarjan 算法的 SCC 检测与缩点过程。核心要点包括：

• dfn/low 双时间戳 是识别 SCC 根节点的关键：当两者相等时触发弹栈。
• 缩点操作 将复杂的有向图转化为 DAG，使动态规划、拓扑排序等工具得以应用。
• 缩点后的 DAG 支持多种高级分析，如最长路径、最小点覆盖、2-SAT 判定等。

理解强连通分量与缩点，是掌握有向图算法体系的必经之路。读者可在此基础上进一步探索：结合 2-SAT 问题建模布尔方程的可满足性，或将缩点应用于程序依赖分析与死锁检测。