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

强连通分量（Strongly Connected Components，简称SCC）是有向图算法中的核心概念。如果一个有向图中任意两个节点互相可达，则称该图是强连通的；强连通分量则是极大的强连通子图。SCC分解在编译器优化、死代码检测、社交网络社区发现、游戏关卡可达性分析等领域有广泛应用。

问题定义

给定有向图 G = (V, E)，将其分解为若干强连通分量，使得每个分量内部任意两节点互相可达，不同分量之间不存在双向路径。

关键概念

• dfn[u]：节点u在DFS中的访问次序（时间戳）
• low[u]：从u出发通过树边和最多一条非树边（回边/横叉边）能到达的最小dfn值
• 当 dfn[u] == low[u] 时，u是一个强连通分量的根

Tarjan算法（O(V + E)）

核心思路

Tarjan算法通过一次深度优先搜索，利用栈维护当前搜索路径上的节点。low 数组记录节点能回溯到的最小时间戳。当 dfn[u] == low[u] 时，说明u无法回到任何更早的节点，从栈中弹出节点直到u，这些节点构成一个强连通分量。

Java实现

import java.util.*;

public class TarjanSCC {

    private int n; // 节点数
    private List<Integer>[] graph; // 邻接表
    private int[] dfn; // 时间戳
    private int[] low; // 能回溯到的最小时间戳
    private boolean[] inStack; // 是否在栈中
    private Stack<Integer> stack; // 维护当前DFS路径
    private boolean[] visited; // 是否被访问
    private int timestamp; // 当前时间戳
    private List<List<Integer>> sccs; // 所有强连通分量
    private int[] sccId; // 每个节点所属的分量编号
    private int sccCount; // 强连通分量数量

    @SuppressWarnings("unchecked")
    public TarjanSCC(int n) {
        this.n = n;
        this.graph = new ArrayList[n];
        this.dfn = new int[n];
        this.low = new int[n];
        this.inStack = new boolean[n];
        this.stack = new Stack<>();
        this.visited = new boolean[n];
        this.timestamp = 0;
        this.sccs = new ArrayList<>();
        this.sccId = new int[n];
        this.sccCount = 0;

        Arrays.fill(dfn, -1);
        Arrays.fill(low, -1);
        Arrays.fill(sccId, -1);

        for (int i = 0; i < n; i++) {
            graph[i] = new ArrayList<>();
        }
    }

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

    /**
     * 执行Tarjan算法，分解所有强连通分量
     */
    public void findSCCs() {
        for (int i = 0; i < n; i++) {
            if (dfn[i] == -1) {
                tarjan(i);
            }
        }
    }

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

        for (int v : graph[u]) {
            if (dfn[v] == -1) {
                // v未被访问，继续DFS
                tarjan(v);
                low[u] = Math.min(low[u], low[v]);
            } else if (inStack[v]) {
                // v在栈中，说明找到回边
                low[u] = Math.min(low[u], dfn[v]);
            }
            // 如果v已被访问但不在栈中，说明v属于已处理的SCC，忽略
        }

        // 如果u是SCC的根节点
        if (dfn[u] == low[u]) {
            List<Integer> scc = new ArrayList<>();
            int v;
            do {
                v = stack.pop();
                inStack[v] = false;
                scc.add(v);
                sccId[v] = sccCount;
            } while (v != u);

            sccs.add(scc);
            sccCount++;
        }
    }

    /**
     * 获取所有强连通分量
     */
    public List<List<Integer>> getSCCs() {
        return sccs;
    }

    /**
     * 获取节点所属的分量编号
     */
    public int getSccId(int u) {
        return sccId[u];
    }

    /**
     * 获取强连通分量数量
     */
    public int getSccCount() {
        return sccCount;
    }

    /**
     * 构建缩点后的DAG（有向无环图）
     */
    @SuppressWarnings("unchecked")
    public List<Integer>[] buildCondensationGraph() {
        List<Integer>[] dag = new ArrayList[sccCount];
        for (int i = 0; i < sccCount; i++) {
            dag[i] = new ArrayList<>();
        }

        Set<String> edges = new HashSet<>(); // 去重边

        for (int u = 0; u < n; u++) {
            for (int v : graph[u]) {
                int su = sccId[u];
                int sv = sccId[v];
                if (su != sv) {
                    String edge = su + "->" + sv;
                    if (!edges.contains(edge)) {
                        edges.add(edge);
                        dag[su].add(sv);
                    }
                }
            }
        }

        return dag;
    }

    public static void main(String[] args) {
        // 构建示例有向图
        // 0 -> 1 -> 2 -> 0 (SCC1)
        // 1 -> 3
        // 3 -> 4 -> 5 -> 3 (SCC2)

        TarjanSCC tarjan = new TarjanSCC(6);
        tarjan.addEdge(0, 1);
        tarjan.addEdge(1, 2);
        tarjan.addEdge(2, 0);
        tarjan.addEdge(1, 3);
        tarjan.addEdge(3, 4);
        tarjan.addEdge(4, 5);
        tarjan.addEdge(5, 3);

        tarjan.findSCCs();

        System.out.println("强连通分量数量: " + tarjan.getSccCount());
        System.out.println("各分量:");
        for (int i = 0; i < tarjan.getSCCs().size(); i++) {
            System.out.println("  SCC " + i + ": " + tarjan.getSCCs().get(i));
        }

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

Kosaraju算法（O(V + E)）

核心思路

Kosaraju算法通过两次DFS实现：
1. 第一次DFS：在原图上按完成时间逆序给节点排序
2. 第二次DFS：在转置图上按上述顺序进行DFS，每次DFS访问到的节点构成一个SCC

Java实现

import java.util.*;

public class KosarajuSCC {

    private int n;
    private List<Integer>[] graph; // 原图
    private List<Integer>[] transpose; // 转置图
    private boolean[] visited;
    private Stack<Integer> finishOrder; // 完成时间顺序
    private List<List<Integer>> sccs;

    @SuppressWarnings("unchecked")
    public KosarajuSCC(int n) {
        this.n = n;
        this.graph = new ArrayList[n];
        this.transpose = new ArrayList[n];
        this.visited = new boolean[n];
        this.finishOrder = new Stack<>();
        this.sccs = new ArrayList<>();

        for (int i = 0; i < n; i++) {
            graph[i] = new ArrayList<>();
            transpose[i] = new ArrayList<>();
        }
    }

    public void addEdge(int from, int to) {
        graph[from].add(to);
        transpose[to].add(from); // 同时构建转置图
    }

    public void findSCCs() {
        // 第一次DFS：确定完成顺序
        Arrays.fill(visited, false);
        for (int i = 0; i < n; i++) {
            if (!visited[i]) {
                dfs1(i);
            }
        }

        // 第二次DFS：在转置图上按逆序处理
        Arrays.fill(visited, false);
        while (!finishOrder.isEmpty()) {
            int u = finishOrder.pop();
            if (!visited[u]) {
                List<Integer> scc = new ArrayList<>();
                dfs2(u, scc);
                sccs.add(scc);
            }
        }
    }

    private void dfs1(int u) {
        visited[u] = true;
        for (int v : graph[u]) {
            if (!visited[v]) {
                dfs1(v);
            }
        }
        finishOrder.push(u);
    }

    private void dfs2(int u, List<Integer> scc) {
        visited[u] = true;
        scc.add(u);
        for (int v : transpose[u]) {
            if (!visited[v]) {
                dfs2(v, scc);
            }
        }
    }

    public List<List<Integer>> getSCCs() {
        return sccs;
    }

    public static void main(String[] args) {
        KosarajuSCC kosaraju = new KosarajuSCC(6);
        kosaraju.addEdge(0, 1);
        kosaraju.addEdge(1, 2);
        kosaraju.addEdge(2, 0);
        kosaraju.addEdge(1, 3);
        kosaraju.addEdge(3, 4);
        kosaraju.addEdge(4, 5);
        kosaraju.addEdge(5, 3);

        kosaraju.findSCCs();

        System.out.println("Kosaraju算法结果:");
        for (int i = 0; i < kosaraju.getSCCs().size(); i++) {
            System.out.println("  SCC " + i + ": " + kosaraju.getSCCs().get(i));
        }
    }
}

缩点与DAG上的动态规划

强连通分量分解的核心价值在于缩点：将每个SCC收缩为一个节点，得到的有向图必然是DAG（有向无环图）。在DAG上可以方便地进行拓扑排序和动态规划。

应用示例：最少加多少条边使有向图强连通

public class MakeStronglyConnected {

    /**
     * 计算使有向图强连通最少需要添加的边数
     * 答案 = max(入度为0的SCC数, 出度为0的SCC数)
     */
    public int minEdgesToAdd(TarjanSCC tarjan) {
        int sccCount = tarjan.getSccCount();
        if (sccCount == 1) return 0; // 已经强连通

        int[] inDegree = new int[sccCount];
        int[] outDegree = new int[sccCount];

        // 统计缩点后的入度和出度
        for (int u = 0; u < tarjan.n; u++) {
            for (int v : tarjan.graph[u]) {
                int su = tarjan.getSccId(u);
                int sv = tarjan.getSccId(v);
                if (su != sv) {
                    outDegree[su]++;
                    inDegree[sv]++;
                }
            }
        }

        int inZero = 0, outZero = 0;
        for (int i = 0; i < sccCount; i++) {
            if (inDegree[i] == 0) inZero++;
            if (outDegree[i] == 0) outZero++;
        }

        return Math.max(inZero, outZero);
    }
}

两种算法的对比

复杂度分析

两种算法的时间复杂度均为 O(V + E)，空间复杂度均为 O(V + E)（邻接表存储）。

实际应用场景

1. 编译器优化：识别循环和控制流图中的基本块
2. 死代码检测：无法从入口到达的SCC即为死代码
3. 网页排名：网页链接图的强连通社区分析
4. 游戏设计：关卡可达性分析和最短通关路径
5. 社交网络：识别紧密互动的用户群体

总结

强连通分量分解揭示了有向图的层次结构。Tarjan算法通过精巧的low值维护实现单次DFS分解，Kosaraju算法则以更直观的两次DFS完成任务。掌握SCC分解，配合缩点技术将复杂有向图转化为DAG，是解决图论高级问题的关键能力。