第3章 循环依赖检测原理
你想想看，一个项目里几十个模块互相引用，如果某个晚上有人不小心引入了一个循环依赖，第二天CI直接挂了，排查起来有多痛苦？我自己就踩过这种坑，而且不止一次。所以这一章我们彻底搞懂循环依赖检测的原理——依赖图怎么构建、DFS怎么找环、拓扑排序怎么兜底。
3.1 依赖图构建：把代码关系变成一张网
检测循环依赖的第一步，是把模块之间的引用关系抽象成一张有向图。每个模块是一个节点，如果 A 引用了 B，就画一条从 A 指向 B 的边。说白了，就是把 import 语句翻译成图结构。
我记得刚接手一个老项目时，发现启动日志里报了一堆「ModuleNotFoundError」，但明明所有依赖都装了。后来一查，是几个工具模块互相引用，形成了循环。当时还没有自动化检测，全靠肉眼盯代码，那叫一个痛苦。
构建依赖图的要点就两个：
- 扫描入口：遍历项目中的所有源文件，解析 import / require / include 语句。
- 建立邻接表：用字典或 Map 存储每个模块的依赖列表，key 是模块名，value 是它依赖的模块集合。
举个例子，Python 项目可以用 ast 模块解析 import 节点，Java 项目可以用 ASM 扫描字节码中的依赖。构建完的图大概长这样：
依赖图（邻接表表示）：
utils → [core, logger]
core → [config]
logger → [core]
config → [] # 无依赖madge 这个工具，它能自动从模块依赖生成可视化图，排查循环依赖非常直观。
3.2 深度优先搜索（DFS）检测环
有了有向图，下一步就是检测有没有环。最实用的方法就是深度优先搜索（DFS）。为什么用 DFS 而不是 BFS？因为 DFS 能天然利用调用栈回溯，发现「走回头路」的情况。
具体做法是给每个节点涂上三种颜色：
| 颜色 | 状态 | 含义 |
|---|---|---|
| 白色 (WHITE) | 未访问 | 还没遍历到这个节点 |
| 灰色 (GRAY) | 正在访问 | 递归栈中，如果再次遇到 → 有环 |
| 黑色 (BLACK) | 已访问完成 | 所有子节点都遍历完了，安全 |
为什么灰色就代表有环？你想想看，如果从 A 出发，沿着边走到 B，又走到 C，突然 C 又指向了 B 且 B 还是灰色，说明我们走了一条「回头路」，环就出现了。这其实就是三色标记法的核心逻辑。
伪代码很简单，但细节里藏着魔鬼：
def has_cycle(graph):
color = {node: WHITE for node in graph}
def dfs(node):
color[node] = GRAY
for neighbor in graph.get(node, []):
if color[neighbor] == GRAY:
return True # 发现环！
if color[neighbor] == WHITE:
if dfs(neighbor):
return True
color[node] = BLACK
return False
for node in graph:
if color[node] == WHITE:
if dfs(node):
return True
return False3.3 拓扑排序：验证依赖顺序
DFS 检测环能告诉我们「有没有问题」，但有时候我们还想知道「依赖的顺序对不对」。这时候就需要拓扑排序了。
拓扑排序只对有向无环图 (DAG) 有效。如果图里有环，拓扑排序就做不了——这也反过来验证了有没有环。我个人习惯在 CI 里先用 DFS 快速检测，如果没环，再用拓扑排序生成依赖顺序，确保构建脚本按正确顺序执行。
最常用的算法是 Kahn 算法，思路特别直白：
- 统计每个节点的入度（有多少条边指向它）。
- 把所有入度为 0 的节点入队（这些模块没有任何前置依赖）。
- 依次出队，每出队一个节点，就把它的邻居入度减 1；如果邻居入度变成 0，也入队。
- 如果最终出队节点数等于总节点数，说明无环；否则说明有环。
说白了，这个过程就像「剥洋葱」，一层层剥掉没有依赖的节点。如果剥到最后还有节点剩下来，那它们肯定构成了一个环。
3.4 实战案例：Python 实现
下面是我在实际项目里用的一个简化版检测器，把上面两个方法都封装进去了。你可以直接把它集成到 CI 脚本中。
from collections import deque
class DependencyChecker:
"""循环依赖检测器：同时支持 DFS 检测和拓扑排序"""
def __init__(self):
self.graph = {} # 邻接表
self.WHITE, self.GRAY, self.BLACK = 0, 1, 2
def add_dependency(self, module, dep):
if module not in self.graph:
self.graph[module] = []
self.graph[module].append(dep)
# 确保依赖节点也在图中
if dep not in self.graph:
self.graph[dep] = []
# ---------- DFS 环检测 ----------
def has_cycle(self):
color = {node: self.WHITE for node in self.graph}
for node in self.graph:
if color[node] == self.WHITE:
if self._dfs(node, color):
return True
return False
def _dfs(self, node, color):
color[node] = self.GRAY
for nb in self.graph.get(node, []):
if color.get(nb) == self.GRAY:
return True
if color.get(nb) == self.WHITE:
if self._dfs(nb, color):
return True
color[node] = self.BLACK
return False
# ---------- 拓扑排序 (Kahn) ----------
def topological_sort(self):
in_degree = {node: 0 for node in self.graph}
for node in self.graph:
for nb in self.graph[node]:
in_degree[nb] = in_degree.get(nb, 0) + 1
queue = deque([n for n in self.graph if in_degree[n] == 0])
result = []
while queue:
node = queue.popleft()
result.append(node)
for nb in self.graph.get(node, []):
in_degree[nb] -= 1
if in_degree[nb] == 0:
queue.append(nb)
return result if len(result) == len(self.graph) else []用法也很简单：先构建图，然后调用 checker.has_cycle()，如果返回 False 再跑 checker.topological_sort() 拿到构建顺序。