深入理解Java强连通分量（手把手教你用Tarjan算法实现图论中的强连通分量）

如上图所示，一个有向图可以被划分为多个强连通分量。每个分量内部的节点互相可达，但不同分量之间则不具备这种性质。

为什么需要找强连通分量？

强连通分量在很多实际问题中有应用，比如：

• 社交网络中识别紧密联系的用户群
• 编译器优化中的控制流分析
• 网页排名（PageRank）中的网页聚类

Tarjan 算法简介

Tarjan 算法是由 Robert Tarjan 提出的一种基于深度优先搜索（DFS）的线性时间算法，用于找出有向图中的所有强连通分量。它的时间复杂度为 O(V + E)，其中 V 是顶点数，E 是边数。

算法核心思想是：在 DFS 过程中，为每个节点维护两个值：

• dfsNum：节点被访问的时间戳
• lowLink：该节点能回溯到的最早祖先的时间戳

当某个节点的 dfsNum == lowLink 时，说明找到了一个强连通分量的“根”，此时栈中从该节点往上的所有节点构成一个 SCC。

Java 实现 Tarjan 算法

下面是一个完整的 Java 示例，演示如何使用 Tarjan 算法找出图中的所有强连通分量。

import java.util.*;public class StronglyConnectedComponents {    private int time;    private List<List<Integer>> graph;    private boolean[] visited;    private int[] dfsNum;    private int[] lowLink;    private Stack<Integer> stack;    private boolean[] inStack;    private List<List<Integer>> sccList;    public StronglyConnectedComponents(List<List<Integer>> graph) {        this.graph = graph;        int n = graph.size();        this.visited = new boolean[n];        this.dfsNum = new int[n];        this.lowLink = new int[n];        this.stack = new Stack<>();        this.inStack = new boolean[n];        this.sccList = new ArrayList<>();        this.time = 0;    }    public void findSCC() {        for (int i = 0; i < graph.size(); i++) {            if (!visited[i]) {                tarjan(i);            }        }    }    private void tarjan(int u) {        visited[u] = true;        dfsNum[u] = lowLink[u] = ++time;        stack.push(u);        inStack[u] = true;        for (int v : graph.get(u)) {            if (!visited[v]) {                tarjan(v);                lowLink[u] = Math.min(lowLink[u], lowLink[v]);            } else if (inStack[v]) {                lowLink[u] = Math.min(lowLink[u], dfsNum[v]);            }        }        // 如果 u 是当前强连通分量的根        if (lowLink[u] == dfsNum[u]) {            List<Integer> component = new ArrayList<>();            int w;            do {                w = stack.pop();                inStack[w] = false;                component.add(w);            } while (w != u);            sccList.add(component);        }    }    public List<List<Integer>> getSCCList() {        return sccList;    }    // 测试示例    public static void main(String[] args) {        // 构建一个有向图：0->1, 1->2, 2->0, 1->3, 3->4, 4->5, 5->3        List<List<Integer>> graph = new ArrayList<>();        for (int i = 0; i < 6; i++) {            graph.add(new ArrayList<>());        }        graph.get(0).add(1);        graph.get(1).add(2);        graph.get(2).add(0);        graph.get(1).add(3);        graph.get(3).add(4);        graph.get(4).add(5);        graph.get(5).add(3);        StronglyConnectedComponents scc = new StronglyConnectedComponents(graph);        scc.findSCC();        System.out.println("找到的强连通分量：");        for (List<Integer> comp : scc.getSCCList()) {            System.out.println(comp);        }    }}

代码说明

上述代码中：

• graph 是邻接表表示的有向图
• tarjan 方法递归执行 DFS 并更新 lowLink
• 使用 stack 保存当前路径上的节点
• 当发现 lowLink[u] == dfsNum[u] 时，弹出栈中元素直到 u，形成一个 SCC

运行结果将输出两个强连通分量：[2, 1, 0] 和 [5, 4, 3]，这与我们预期一致。

总结

通过本教程，你已经学会了如何在 Java 中实现 强连通分量Tarjan 算法。这是 图论算法 中的经典问题，也是面试高频考点。建议你动手运行代码，修改图结构，加深理解。

记住，掌握 Java强连通分量 不仅能提升你的算法能力，还能为你解决复杂系统问题打下坚实基础！