每日算法 — 使用java实现Tarjan算法：强连通分量与割点割边的高效求解

在图论中，强连通分量（Strongly Connected Component, SCC）是指有向图中任意两个顶点互相可达的最大子图。求解 SCC 是编译器优化、社交网络分析、死锁检测等领域的核心问题。Tarjan 算法由 Robert Tarjan 于 1972 年提出，仅用一次深度优先搜索（DFS）即可在 (O(V+E)) 时间内找出所有强连通分量，是图论算法中最优雅的实现之一。本文将完整实现 Tarjan 算法，并扩展到割点与割边的求解。

核心概念

强连通分量（SCC）

在有向图 (G=(V,E)) 中，若子图 (G’) 中任意两点 (u,v) 都存在从 (u) 到 (v) 和从 (v) 到 (u) 的路径，则称 (G’) 为强连通分量。

Tarjan 算法的关键变量

• dfn[u]：节点 u 在 DFS 中的访问次序（时间戳）。
• low[u]：节点 u 及其后代节点通过回边能追溯到的最早祖先的 dfn 值。
• 栈：维护当前 DFS 路径上的节点，用于提取 SCC。

判定条件：当 dfn[u] == low[u] 时，说明 u 是其所在 SCC 的”根”，将栈中节点依次弹出直到 u，即构成一个 SCC。

Tarjan 算法完整实现

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

public class TarjanSCC {

    private final List<List<Integer>> graph;
    private final int n;
    private int[] dfn;       // 时间戳
    private int[] low;       // 能追溯到的最早祖先
    private boolean[] inStack;
    private int timestamp;   // 当前时间戳计数器
    private final Stack<Integer> stack;
    private final List<List<Integer>> sccs; // 存储所有强连通分量

    public TarjanSCC(List<List<Integer>> graph) {
        this.graph = graph;
        this.n = graph.size();
        this.dfn = new int[n];
        this.low = new int[n];
        this.inStack = new boolean[n];
        this.timestamp = 0;
        this.stack = new Stack<>();
        this.sccs = new ArrayList<>();

        // 初始化 dfn 为 -1 表示未访问
        for (int i = 0; i < n; i++) {
            dfn[i] = -1;
        }
    }

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

    private void dfs(int u) {
        // 初始化 u 的时间戳和 low 值
        dfn[u] = low[u] = ++timestamp;
        stack.push(u);
        inStack[u] = true;

        // 遍历 u 的所有邻接点
        for (int v : graph.get(u)) {
            if (dfn[v] == -1) {
                // v 未被访问，继续 DFS
                dfs(v);
                // 回溯时更新 low[u]
                low[u] = Math.min(low[u], low[v]);
            } else if (inStack[v]) {
                // v 在栈中，说明 (u,v) 是回边，更新 low[u]
                low[u] = Math.min(low[u], dfn[v]);
            }
            // 若 v 已访问但不在栈中，说明 v 属于另一个 SCC，无需处理
        }

        // 若 u 是 SCC 的根，则弹出栈中节点构成一个 SCC
        if (dfn[u] == low[u]) {
            List<Integer> scc = new ArrayList<>();
            int v;
            do {
                v = stack.pop();
                inStack[v] = false;
                scc.add(v);
            } while (v != u);
            sccs.add(scc);
            System.out.println("发现强连通分量: " + scc);
        }
    }

    /**
     * 构建缩点后的 DAG（有向无环图）
     */
    public List<List<Integer>> condenseDAG() {
        int[] sccId = new int[n];
        for (int i = 0; i < sccs.size(); i++) {
            for (int node : sccs.get(i)) {
                sccId[node] = i;
            }
        }

        List<List<Integer>> dag = new ArrayList<>();
        for (int i = 0; i < sccs.size(); i++) {
            dag.add(new ArrayList<>());
        }

        boolean[][] visited = new boolean[sccs.size()][sccs.size()];
        for (int u = 0; u < n; u++) {
            for (int v : graph.get(u)) {
                if (sccId[u] != sccId[v] && !visited[sccId[u]][sccId[v]]) {
                    dag.get(sccId[u]).add(sccId[v]);
                    visited[sccId[u]][sccId[v]] = true;
                }
            }
        }
        return dag;
    }

    public static void main(String[] args) {
        int n = 8;
        List<List<Integer>> graph = new ArrayList<>();
        for (int i = 0; i < n; i++) graph.add(new ArrayList<>());

        // 构建示例有向图
        graph.get(0).add(1);
        graph.get(1).add(2);
        graph.get(2).add(0); // 0-1-2 构成 SCC
        graph.get(2).add(3);
        graph.get(3).add(4);
        graph.get(4).add(5);
        graph.get(5).add(3); // 3-4-5 构成 SCC
        graph.get(6).add(5);
        graph.get(6).add(7);
        graph.get(7).add(6); // 6-7 构成 SCC

        System.out.println("===== Tarjan 算法求解强连通分量 =====\n");
        TarjanSCC tarjan = new TarjanSCC(graph);
        List<List<Integer>> sccs = tarjan.findSCCs();

        System.out.println("\n===== 结果汇总 =====");
        System.out.println("图中共有 " + sccs.size() + " 个强连通分量");
        for (int i = 0; i < sccs.size(); i++) {
            System.out.println("SCC " + (i + 1) + ": " + sccs.get(i));
        }

        // 缩点
        List<List<Integer>> dag = tarjan.condenseDAG();
        System.out.println("\n===== 缩点后的 DAG =====");
        for (int i = 0; i < dag.size(); i++) {
            System.out.println("组件 " + i + " -> " + dag.get(i));
        }
    }
}

割点（Articulation Point）求解

在无向连通图中，若删除某顶点及其关联边后，图的连通分量数量增加，则该顶点为割点。Tarjan 算法同样可以高效求解割点：

public class TarjanCutVertex {

    private final List<List<Integer>> graph;
    private final int n;
    private int[] dfn;
    private int[] low;
    private boolean[] isCutVertex;
    private int timestamp;
    private int root; // 当前 DFS 树根节点
    private int rootChildren; // 根节点的子树数量

    public TarjanCutVertex(List<List<Integer>> graph) {
        this.graph = graph;
        this.n = graph.size();
        this.dfn = new int[n];
        this.low = new int[n];
        this.isCutVertex = new boolean[n];
        this.timestamp = 0;

        for (int i = 0; i < n; i++) {
            dfn[i] = -1;
        }
    }

    public List<Integer> findCutVertices() {
        List<Integer> cutVertices = new ArrayList<>();

        for (int i = 0; i < n; i++) {
            if (dfn[i] == -1) {
                root = i;
                rootChildren = 0;
                dfs(i, -1);
                // 根节点若有超过一个子树，则是割点
                if (rootChildren > 1) {
                    isCutVertex[root] = true;
                }
            }
        }

        for (int i = 0; i < n; i++) {
            if (isCutVertex[i]) {
                cutVertices.add(i);
            }
        }
        return cutVertices;
    }

    private void dfs(int u, int parent) {
        dfn[u] = low[u] = ++timestamp;
        int children = 0;

        for (int v : graph.get(u)) {
            if (v == parent) continue;

            if (dfn[v] == -1) {
                children++;
                if (u == root) rootChildren++;

                dfs(v, u);
                low[u] = Math.min(low[u], low[v]);

                // 割点判定：u 不是根，且 v 无法回溯到 u 的祖先
                if (u != root && low[v] >= dfn[u]) {
                    isCutVertex[u] = true;
                }
            } else {
                // v 已访问，回边更新 low[u]
                low[u] = Math.min(low[u], dfn[v]);
            }
        }
    }

    public static void main(String[] args) {
        int n = 6;
        List<List<Integer>> graph = new ArrayList<>();
        for (int i = 0; i < n; i++) graph.add(new ArrayList<>());

        // 构建无向图
        addUndirectedEdge(graph, 0, 1);
        addUndirectedEdge(graph, 0, 2);
        addUndirectedEdge(graph, 1, 2);
        addUndirectedEdge(graph, 1, 3);
        addUndirectedEdge(graph, 3, 4);
        addUndirectedEdge(graph, 3, 5);

        TarjanCutVertex tarjan = new TarjanCutVertex(graph);
        List<Integer> cutVertices = tarjan.findCutVertices();
        System.out.println("割点: " + cutVertices); // [1, 3]
    }

    private static void addUndirectedEdge(List<List<Integer>> g, int u, int v) {
        g.get(u).add(v);
        g.get(v).add(u);
    }
}

割边（Bridge）求解

若删除某条边后，图的连通分量数量增加，则该边为割边（桥）：

public class TarjanBridge {

    private final List<List<Integer>> graph;
    private final int n;
    private int[] dfn;
    private int[] low;
    private final List<int[]> bridges;
    private int timestamp;

    public TarjanBridge(List<List<Integer>> graph) {
        this.graph = graph;
        this.n = graph.size();
        this.dfn = new int[n];
        this.low = new int[n];
        this.bridges = new ArrayList<>();
        this.timestamp = 0;

        for (int i = 0; i < n; i++) {
            dfn[i] = -1;
        }
    }

    public List<int[]> findBridges() {
        for (int i = 0; i < n; i++) {
            if (dfn[i] == -1) {
                dfs(i, -1);
            }
        }
        return bridges;
    }

    private void dfs(int u, int parent) {
        dfn[u] = low[u] = ++timestamp;

        for (int v : graph.get(u)) {
            if (v == parent) continue;

            if (dfn[v] == -1) {
                dfs(v, u);
                low[u] = Math.min(low[u], low[v]);

                // 割边判定：v 无法回溯到 u 或其祖先
                if (low[v] > dfn[u]) {
                    bridges.add(new int[]{u, v});
                    System.out.println("发现割边: (" + u + ", " + v + ")");
                }
            } else {
                low[u] = Math.min(low[u], dfn[v]);
            }
        }
    }

    public static void main(String[] args) {
        int n = 5;
        List<List<Integer>> graph = new ArrayList<>();
        for (int i = 0; i < n; i++) graph.add(new ArrayList<>());

        addUndirectedEdge(graph, 0, 1);
        addUndirectedEdge(graph, 1, 2);
        addUndirectedEdge(graph, 2, 0); // 0-1-2 构成环
        addUndirectedEdge(graph, 1, 3);
        addUndirectedEdge(graph, 3, 4); // (1,3) 和 (3,4) 是割边

        TarjanBridge tarjan = new TarjanBridge(graph);
        List<int[]> bridges = tarjan.findBridges();
        System.out.println("\n所有割边:");
        for (int[] b : bridges) {
            System.out.println("(" + b[0] + ", " + b[1] + ")");
        }
    }

    private static void addUndirectedEdge(List<List<Integer>> g, int u, int v) {
        g.get(u).add(v);
        g.get(v).add(u);
    }
}

实战应用：社交网络关键人物识别

在社交关系网络中，将每个人视为节点，关注关系视为有向边。强连通分量代表了”小圈子”——圈内成员互相关注；而割点则代表了”关键人物”——删除该人物会导致社交网络分裂：

/**
 * 社交网络分析器
 */
public class SocialNetworkAnalyzer {

    public static void analyze(List<List<Integer>> followGraph, String[] userNames) {
        // 1. 找出所有"小圈子"（强连通分量）
        TarjanSCC tarjan = new TarjanSCC(followGraph);
        List<List<Integer>> sccs = tarjan.findSCCs();

        System.out.println("===== 社交网络分析报告 =====");
        System.out.println("平台共有 " + sccs.size() + " 个互相关注的小圈子\n");

        for (int i = 0; i < sccs.size(); i++) {
            List<Integer> scc = sccs.get(i);
            System.out.print("圈子 " + (i + 1) + "（" + scc.size() + "人）: ");
            for (int uid : scc) {
                System.out.print(userNames[uid] + " ");
            }
            System.out.println();
        }

        // 2. 构建无向图分析关键人物
        List<List<Integer>> undirected = new ArrayList<>();
        for (int i = 0; i < followGraph.size(); i++) undirected.add(new ArrayList<>());
        for (int u = 0; u < followGraph.size(); u++) {
            for (int v : followGraph.get(u)) {
                if (!undirected.get(u).contains(v)) {
                    undirected.get(u).add(v);
                    undirected.get(v).add(u);
                }
            }
        }

        TarjanCutVertex cutVertexFinder = new TarjanCutVertex(undirected);
        List<Integer> keyUsers = cutVertexFinder.findCutVertices();

        System.out.println("\n关键人物（删除后网络会分裂）:");
        for (int uid : keyUsers) {
            System.out.println("  - " + userNames[uid]);
        }
    }
}

复杂度分析

Tarjan 算法的线性时间复杂度使其成为处理大规模图数据的首选算法。

总结

Tarjan 算法通过巧妙维护 dfn 和 low 两个时间戳数组，在一次 DFS 中同时完成强连通分量、割点和割边的判定。其核心思想——”通过回边追溯最早祖先”——不仅是图论算法的经典范式，更在编译器的控制流分析、操作系统的死锁检测、互联网的拓扑分析等场景中广泛应用。掌握 Tarjan 算法，意味着你拥有了一把剖析图结构的”瑞士军刀”。