Tarjan算法详解（Java语言实现强连通分量识别）

Tarjan算法核心思想

Tarjan算法利用深度优先搜索（DFS）遍历图，并为每个节点维护两个关键值：

• dfn[u]：节点u被访问的时间戳（即DFS序号）
• low[u]：节点u或其子树能够追溯到的最早的栈中节点的dfn值

算法使用一个栈来保存当前路径上的节点。当某个节点u满足dfn[u] == low[u]时，说明找到了一个强连通分量的根节点，此时从栈中弹出所有属于该分量的节点。

Java实现步骤

1. 初始化图结构、时间戳、dfn数组、low数组、栈和访问标记
2. 对每个未访问的节点执行DFS
3. 在DFS过程中更新dfn和low值
4. 判断是否找到强连通分量并输出

完整Java代码示例

import java.util.*;public class TarjanSCC {    private List<List<Integer>> graph;    private int[] dfn;    private int[] low;    private boolean[] inStack;    private Stack<Integer> stack;    private int time;    private List<List<Integer>> sccList;    public TarjanSCC(int n) {        graph = new ArrayList<>();        for (int i = 0; i < n; i++) {            graph.add(new ArrayList<>());        }        dfn = new int[n];        low = new int[n];        inStack = new boolean[n];        stack = new Stack<>();        time = 0;        sccList = new ArrayList<>();    }    public void addEdge(int u, int v) {        graph.get(u).add(v);    }    public void tarjan(int u) {        dfn[u] = low[u] = ++time;        stack.push(u);        inStack[u] = true;        for (int v : graph.get(u)) {            if (dfn[v] == 0) { // 未访问过                tarjan(v);                low[u] = Math.min(low[u], low[v]);            } else if (inStack[v]) { // 在栈中，说明是回边                low[u] = Math.min(low[u], dfn[v]);            }        }        // 如果u是强连通分量的根        if (dfn[u] == low[u]) {            List<Integer> scc = new ArrayList<>();            while (true) {                int node = stack.pop();                inStack[node] = false;                scc.add(node);                if (node == u) break;            }            sccList.add(scc);        }    }    public List<List<Integer>> findSCC() {        Arrays.fill(dfn, 0);        for (int i = 0; i < graph.size(); i++) {            if (dfn[i] == 0) {                tarjan(i);            }        }        return sccList;    }    public static void main(String[] args) {        // 示例：创建一个有向图        TarjanSCC tarjan = new TarjanSCC(5);        tarjan.addEdge(0, 1);        tarjan.addEdge(1, 2);        tarjan.addEdge(2, 0);        tarjan.addEdge(1, 3);        tarjan.addEdge(3, 4);        List<List<Integer>> sccs = tarjan.findSCC();        System.out.println("强连通分量如下：");        for (List<Integer> scc : sccs) {            System.out.println(scc);        }    }}  

代码说明

上述代码实现了完整的Tarjan算法：

• graph：邻接表存储图
• dfn 和 low：记录时间戳和最早可达祖先
• stack：用于追踪当前DFS路径
• tarjan()：递归执行DFS并更新low值
• findSCC()：对外接口，返回所有强连通分量

运行结果

对于示例图（0→1→2→0，1→3→4），程序将输出：

强连通分量如下：[2, 1, 0][4][3]  

总结

Tarjan算法是解决强连通分量问题的利器，广泛应用于编译器优化、社交网络分析、依赖解析等领域。通过本教程，你已经掌握了如何用Java语言实现Tarjan算法。记住，理解图论算法的关键在于动手实践——尝试修改图结构、添加更多测试用例，你会对算法有更深的体会！

希望这篇关于Java实现Tarjan的教程对你有所帮助。如果你有任何疑问，欢迎在评论区留言交流！