Tarjan算法解 强连通分量 循环依赖

目录一、核心概念强连通分量 循环依赖1. 基础定义2. 两种图存储结构对比3. Tarjan 算法原理求强连通分量核心变量算法流程二、完整 Java 实战实现通用工具常量 基础封装一、邻接矩阵 版本1. 邻接矩阵图结构 Tarjan 依赖检测二、邻接表 版本生产推荐三、核心循环依赖判断逻辑四、测试入口 多场景用例三、运行结果说明四、关键点解析 生产优化1. 两种存储选型2. Tarjan 时间复杂度3. 业务场景扩展4. 边界问题处理五、补充简易总结判断逻辑一、核心概念强连通分量 循环依赖1. 基础定义有向图节点间边有方向依赖场景天然是有向图A→B 代表 A 依赖 B。强连通分量 (SCC)有向图中任意两个节点互相可达的最大子图。循环依赖判定规则若单个强连通分量内节点数 ≥ 2必然存在循环依赖节点互相引用若强连通分量只有1 个节点分两种节点存在自环自己依赖自己→ 也算循环依赖无自环 → 无循环依赖。2. 两种图存储结构对比存储结构优点缺点适用场景邻接矩阵实现简单、判边快空间复杂度 \(O(n^2)\)节点多则浪费节点数量少百级以内邻接表空间 \(O(nm)\)m 为边数稀疏图高效遍历邻接点稍繁琐业务依赖图绝大多数场景3. Tarjan 算法原理求强连通分量核心变量dfn[]时间戳记录节点首次被访问的次序low[]节点或其可达子树中最小的 dfn 值栈保存当前遍历路径上的节点inStack[]标记节点是否在栈中。算法流程遍历所有未访问节点启动 DFS进入节点 u初始化dfn[u] low[u] 时间戳u 入栈、标记在栈中遍历 u 的所有邻接节点 vv 未访问递归 DFS (v)回溯后更新low[u] min(low[u], low[v])v 已访问且在栈中更新low[u] min(low[u], dfn[v])若遍历完所有邻接点后dfn[u] low[u]说明 u 是当前强连通分量的根不断弹栈直到 u 出栈弹出的所有节点构成一个 SCC对每个 SCC按规则判断是否存在循环依赖。二、完整 Java 实战实现分为三部分邻接矩阵实现 Tarjan 循环依赖检测邻接表实现 Tarjan 循环依赖检测生产常用测试用例普通依赖、双向循环、自环、多节点环通用工具常量 基础封装import java.util.*; /** * 有向图循环依赖检测基于Tarjan求强连通分量 * 支持邻接矩阵、邻接表两种存储 */ public class CycleDependencyDetector { // 全局时间戳 private int timeStamp; // dfn: 节点访问时间戳 private int[] dfn; // low: 节点能回溯到的最小时间戳 private int[] low; // 标记节点是否在栈中 private boolean[] inStack; // 遍历用栈 private DequeInteger stack; // 最终所有强连通分量 private ListListInteger sccList; public CycleDependencyDetector() {}一、邻接矩阵 版本1. 邻接矩阵图结构 Tarjan 依赖检测// 邻接矩阵实现 /** * param graph 邻接矩阵 graph[u][v] 1 表示 u - v 存在依赖边 * param nodeCount 节点总数节点编号0 ~ nodeCount-1 * return true: 存在循环依赖 false: 无循环依赖 */ public boolean checkByMatrix(int[][] graph, int nodeCount) { // 初始化数组 timeStamp 0; dfn new int[nodeCount]; low new int[nodeCount]; inStack new boolean[nodeCount]; stack new ArrayDeque(); sccList new ArrayList(); // 初始化为0表示未访问 Arrays.fill(dfn, 0); Arrays.fill(low, 0); // 遍历所有节点防止非连通图 for (int i 0; i nodeCount; i) { if (dfn[i] 0) { tarjanMatrix(i, graph, nodeCount); } } // 遍历所有强连通分量判断是否存在循环依赖 return judgeCycle(graph, sccList); } /** * Tarjan 算法 - 邻接矩阵版 DFS */ private void tarjanMatrix(int u, int[][] graph, int nodeCount) { // 标记访问时间 dfn[u] low[u] timeStamp; stack.push(u); inStack[u] true; // 遍历所有节点找 u 的邻接点 v for (int v 0; v nodeCount; v) { // u - v 有边 if (graph[u][v] 1) { if (dfn[v] 0) { // 未访问递归 tarjanMatrix(v, graph, nodeCount); // 回溯更新low low[u] Math.min(low[u], low[v]); } else if (inStack[v]) { // 已访问且在栈中属于当前环 low[u] Math.min(low[u], dfn[v]); } } } // dfn[u] low[u] 找到一个强连通分量 if (dfn[u] low[u]) { ListInteger scc new ArrayList(); int cur; do { cur stack.pop(); inStack[cur] false; scc.add(cur); } while (cur ! u); sccList.add(scc); } }二、邻接表 版本生产推荐稀疏依赖图绝大多数业务场景优先使用邻接表空间效率极高。// 邻接表实现推荐 /** * param adj 邻接表 adj.get(u) 存放 u 指向的所有节点 * param nodeCount 节点总数 * return true: 存在循环依赖 */ public boolean checkByAdjList(ListListInteger adj, int nodeCount) { timeStamp 0; dfn new int[nodeCount]; low new int[nodeCount]; inStack new boolean[nodeCount]; stack new ArrayDeque(); sccList new ArrayList(); Arrays.fill(dfn, 0); Arrays.fill(low, 0); for (int i 0; i nodeCount; i) { if (dfn[i] 0) { tarjanAdj(i, adj); } } return judgeCycleByList(adj, sccList); } /** * Tarjan 算法 - 邻接表版 DFS */ private void tarjanAdj(int u, ListListInteger adj) { dfn[u] low[u] timeStamp; stack.push(u); inStack[u] true; // 直接遍历 u 的所有邻接点 for (int v : adj.get(u)) { if (dfn[v] 0) { tarjanAdj(v, adj); low[u] Math.min(low[u], low[v]); } else if (inStack[v]) { low[u] Math.min(low[u], dfn[v]); } } // 弹出整个强连通分量 if (dfn[u] low[u]) { ListInteger scc new ArrayList(); int cur; do { cur stack.pop(); inStack[cur] false; scc.add(cur); } while (cur ! u); sccList.add(scc); } }三、核心循环依赖判断逻辑分别适配邻接矩阵和邻接表统一判断规则SCC 节点数 1 → 循环依赖SCC 节点数 1 → 检查自环自己依赖自己→ 有自环也判定为循环依赖。// 循环依赖判断逻辑 /** * 邻接矩阵版 依赖判断 */ private boolean judgeCycle(int[][] graph, ListListInteger sccList) { for (ListInteger scc : sccList) { int size scc.size(); // 情况1分量节点数≥2必然循环依赖 if (size 1) { printSCC(scc); return true; } // 情况2单个节点判断是否存在自环 u-u int u scc.get(0); if (graph[u][u] 1) { System.out.println(检测到自环节点 u); return true; } } return false; } /** * 邻接表版 依赖判断 */ private boolean judgeCycleByList(ListListInteger adj, ListListInteger sccList) { for (ListInteger scc : sccList) { int size scc.size(); if (size 1) { printSCC(scc); return true; } // 单个节点判自环 int u scc.get(0); if (adj.get(u).contains(u)) { System.out.println(检测到自环节点 u); return true; } } return false; } /** * 打印强连通分量用于日志/调试 */ private void printSCC(ListInteger scc) { System.out.print(发现循环依赖的强连通分量); for (Integer node : scc) { System.out.print(node ); } System.out.println(); }四、测试入口 多场景用例覆盖无依赖、双向循环、三节点环、自环四大典型场景// 测试主方法 public static void main(String[] args) { CycleDependencyDetector detector new CycleDependencyDetector(); // 场景1邻接矩阵测试 - 双向循环依赖 0-1 System.out.println( 场景1邻接矩阵 - 双向循环依赖 ); int[][] matrix1 { {0, 1, 0}, // 0→1 {1, 0, 0}, // 1→0 {0, 0, 0} // 2 无依赖 }; boolean hasCycle1 detector.checkByMatrix(matrix1, 3); System.out.println(是否存在循环依赖 hasCycle1 \n); // 场景2邻接矩阵测试 - 自环 0→0 System.out.println( 场景2邻接矩阵 - 节点自环 ); int[][] matrix2 { {1, 0, 0}, {0, 0, 0}, {0, 0, 0} }; boolean hasCycle2 detector.checkByMatrix(matrix2, 3); System.out.println(是否存在循环依赖 hasCycle2 \n); // 场景3邻接表测试 - 正常单向依赖无循环 0→1→2 System.out.println( 场景3邻接表 - 单向依赖无循环 ); ListListInteger adj1 new ArrayList(); for (int i 0; i 3; i) adj1.add(new ArrayList()); adj1.get(0).add(1); adj1.get(1).add(2); boolean hasCycle3 detector.checkByAdjList(adj1, 3); System.out.println(是否存在循环依赖 hasCycle3 \n); // 场景4邻接表测试 - 三节点环 0→1→2→0 System.out.println( 场景4邻接表 - 三节点循环依赖 ); ListListInteger adj2 new ArrayList(); for (int i 0; i 3; i) adj2.add(new ArrayList()); adj2.get(0).add(1); adj2.get(1).add(2); adj2.get(2).add(0); boolean hasCycle4 detector.checkByAdjList(adj2, 3); System.out.println(是否存在循环依赖 hasCycle4); } }三、运行结果说明 场景1邻接矩阵 - 双向循环依赖 发现循环依赖的强连通分量1 0 是否存在循环依赖true 场景2邻接矩阵 - 节点自环 检测到自环节点0 是否存在循环依赖true 场景3邻接表 - 单向依赖无循环 是否存在循环依赖false 场景4邻接表 - 三节点循环依赖 发现循环依赖的强连通分量2 1 0 是否存在循环依赖true四、关键点解析 生产优化1. 两种存储选型邻接矩阵仅用于节点数少500、教学 / 简单工具场景节点一多内存爆炸邻接表项目中类加载依赖、Bean 依赖、接口调用依赖全部用邻接表。2. Tarjan 时间复杂度邻接矩阵\(O(n^2)\)邻接表\(O(nm)\)n 节点m 边线性复杂度性能最优。3. 业务场景扩展Spring Bean 循环依赖本质就是有向图循环依赖底层思想和本题一致包 / 类依赖校验代码架构校验工具常用 Tarjan 检测包循环引用权限 / 流程节点循环工作流节点互相引用也可用该算法检测。4. 边界问题处理孤立节点无边单个节点、无自环 → 无循环多连通图代码中全量遍历所有节点保证非连通图也能全部检测重复边业务中依赖重复不影响算法天然兼容。五、补充简易总结判断逻辑用 Tarjan 拆分出所有强连通分量分量节点数 1 → 循环依赖分量只有 1 个节点 → 检查是否自环有则循环依赖全部分量都不满足 → 无循环依赖。