每日算法 — 使用java实现SCC：Tarjan算法求解强连通分量

引言

强连通分量（Strongly Connected Component，SCC）是有向图中的重要概念。如果图中任意两个顶点互相可达，则称该图是强连通的；强连通分量则是极大的强连通子图。SCC在编译器优化（控制流分析）、社交网络分析（社区发现）、网页排名（死链检测）等领域有广泛应用。本文用Java实现Tarjan算法，基于深度优先搜索（DFS）和 lowlink 值在 O(V+E) 时间内求解有向图的所有强连通分量。

问题定义

输入：有向图 G = (V, E)，用邻接表表示。
输出：图中所有的强连通分量。

示例：
– 顶点 0→1→2→0 构成一个环（强连通）
– 顶点 3→4，但 4 不能到达 3（各自为独立SCC）

Tarjan算法原理

核心概念

dfn[u]：节点 u 在DFS中的访问序号（时间戳）
low[u]：从 u 出发通过树边和回边能到达的最小dfn值

关键判定

当一个节点的 low[u] == dfn[u] 时，说明 u 是一个强连通分量的”根”——从 u 出发无法通过回边到达更早访问的节点。此时将栈中从 u 开始的所有节点弹出，构成一个SCC。

算法步骤

对每个未访问的节点进行DFS
访问节点 u 时，记录 dfn[u] 和 low[u]，将 u 压入栈
遍历 u 的所有邻接点 v：
如果 v 未访问，递归访问 v，然后 low[u] = min(low[u], low[v])
如果 v 已访问且在栈中，low[u] = min(low[u], dfn[v])
DFS结束后，如果 low[u] == dfn[u]，弹出栈中节点直到 u，构成一个SCC

Java实现

import java.util.*;

public class TarjanSCC {

    private int n;                    // 节点数量
    private List<Integer>[] graph;    // 邻接表
    private int[] dfn;                // 访问时间戳
    private int[] low;                // 能到达的最小时间戳
    private boolean[] inStack;        // 是否在栈中
    private Deque<Integer> stack;     // 手动栈
    private int timestamp;            // 当前时间戳
    private List<List<Integer>> sccs; // 所有强连通分量

    public TarjanSCC(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.timestamp = 0;
        this.sccs = new ArrayList<>();

        // 初始化为-1表示未访问
        Arrays.fill(dfn, -1);
        Arrays.fill(low, -1);
    }

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

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

    /**
     * Tarjan DFS核心
     */
    private void tarjan(int u) {
        // 记录访问时间戳
        dfn[u] = low[u] = ++timestamp;
        stack.push(u);
        inStack[u] = true;

        // 遍历所有邻接点
        for (int v : graph[u]) {
            if (dfn[v] == -1) {
                // v 未访问，继续DFS
                tarjan(v);
                // 回溯时更新low值
                low[u] = Math.min(low[u], low[v]);
            } else if (inStack[v]) {
                // v 已访问且在栈中，说明是回边
                // 更新low[u]为v的dfn值（不是low[v]！）
                low[u] = Math.min(low[u], dfn[v]);
            }
            // 如果v已访问但不在栈中，说明v属于已完成的SCC，忽略
        }

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

    /**
     * 获取缩点后的DAG邻接表（SCC图）
     */
    public List<Integer>[] condenseGraph() {
        findSCCs();

        int sccCount = sccs.size();
        int[] belong = new int[n]; // 每个节点属于哪个SCC
        for (int i = 0; i < sccCount; i++) {
            for (int node : sccs.get(i)) {
                belong[node] = i;
            }
        }

        // 构建DAG
        Set<Integer>[] dagSet = new HashSet[sccCount];
        for (int i = 0; i < sccCount; i++) {
            dagSet[i] = new HashSet<>();
        }

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

        List<Integer>[] dag = new ArrayList[sccCount];
        for (int i = 0; i < sccCount; i++) {
            dag[i] = new ArrayList<>(dagSet[i]);
        }

        return dag;
    }

    public static void main(String[] args) {
        // 示例图：
        // 0 → 1 → 2 → 0 (SCC: {0,1,2})
        // 1 → 3
        // 3 → 4
        // 4 → 5 → 3 (SCC: {3,4,5})
        TarjanSCC solver = new TarjanSCC(6);
        solver.addEdge(0, 1);
        solver.addEdge(1, 2);
        solver.addEdge(2, 0);
        solver.addEdge(1, 3);
        solver.addEdge(3, 4);
        solver.addEdge(4, 5);
        solver.addEdge(5, 3);

        List<List<Integer>> sccs = solver.findSCCs();
        System.out.println("强连通分量数量: " + sccs.size());
        for (int i = 0; i < sccs.size(); i++) {
            System.out.println("SCC " + (i + 1) + ": " + sccs.get(i));
        }

        // 缩点后的DAG
        List<Integer>[] dag = solver.condenseGraph();
        System.out.println("\n缩点后的DAG邻接表:");
        for (int i = 0; i < dag.length; i++) {
            System.out.println("SCC " + i + " -> " + dag[i]);
        }
    }
}

Kosaraju算法对比

import java.util.*;

public class KosarajuSCC {

    private int n;
    private List<Integer>[] graph;
    private List<Integer>[] reverseGraph;
    private boolean[] visited;
    private List<Integer> order;

    public KosarajuSCC(int n) {
        this.n = n;
        this.graph = new ArrayList[n];
        this.reverseGraph = new ArrayList[n];
        for (int i = 0; i < n; i++) {
            graph[i] = new ArrayList<>();
            reverseGraph[i] = new ArrayList<>();
        }
        this.visited = new boolean[n];
        this.order = new ArrayList<>();
    }

    public void addEdge(int u, int v) {
        graph[u].add(v);
        reverseGraph[v].add(u);
    }

    public List<List<Integer>> findSCCs() {
        // 第一遍DFS：确定 finishing order
        for (int i = 0; i < n; i++) {
            if (!visited[i]) {
                dfs1(i);
            }
        }

        // 第二遍DFS：在反向图上按逆序处理
        Arrays.fill(visited, false);
        List<List<Integer>> sccs = new ArrayList<>();

        for (int i = order.size() - 1; i >= 0; i--) {
            int u = order.get(i);
            if (!visited[u]) {
                List<Integer> scc = new ArrayList<>();
                dfs2(u, scc);
                sccs.add(scc);
            }
        }

        return sccs;
    }

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

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

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

        List<List<Integer>> sccs = solver.findSCCs();
        System.out.println("Kosaraju SCC数量: " + sccs.size());
        for (int i = 0; i < sccs.size(); i++) {
            System.out.println("SCC " + (i + 1) + ": " + sccs.get(i));
        }
    }
}

复杂度分析

算法	时间复杂度	空间复杂度	特点
Tarjan	O(V+E)	O(V)	一遍DFS，代码紧凑
Kosaraju	O(V+E)	O(V+E)	两遍DFS，需建反向图

应用场景

2-SAT问题求解：将每个变量拆成两个节点（真/假），通过SCC判断是否可满足
缩点构建DAG：将每个SCC缩为一个节点，得到有向无环图，便于拓扑排序
死锁检测：资源分配图中寻找环路（SCC大小>1表示死锁）
网页链接分析：识别互相引用的网页簇
编译器控制流分析：寻找程序中的循环结构

总结

Tarjan算法是求解有向图强连通分量的经典线性算法。通过维护dfn和low两个关键数组，巧妙地识别出每个SCC的”根节点”。理解Tarjan算法不仅能解决SCC问题，其核心的 lowlink 思想也是求解割点、割边、双连通分量等问题的基础。配合缩点技术，可以将任意有向图转化为DAG，进而应用拓扑排序等工具解决更复杂的问题。

Tagged with: lowlink SCC Tarjan算法强连通分量深度优先搜索