数据结构与算法 / 系统课时
DFS 怎样检测有向环
DFS 怎样检测有向环
在有向依赖图中,普通的“访问过”标记不足以判断环,因为一条边指向已经完成搜索的节点并不代表回到了当前路径。DFS 检测有向环的关键是区分“正在递归路径中”和“已经处理完成”两种状态,并在遇到回边时立即判定有环。
学习目标
- 理解三色状态在有向图 DFS 中分别表示什么
- 能用递归栈状态识别指向当前路径的回边
- 能判断 DFS 环检测的复杂度与适用边界
为什么需要三种状态
对每个节点维护三个状态即可:
0:未访问,还没有进入 DFS1:访问中,节点仍在当前递归调用链上2:已完成,该节点及其后继都已经检查完
从 u 遍历到 v 时,如果 v 的状态是 1,说明 v 仍位于当前 DFS 路径中。此时存在一条从后代重新指向祖先的回边,因此形成有向环。若 v 已经是 2,它不在当前路径中,不能据此判环。

用递归状态检测环
下面的实现为每个节点维护三色状态。进入 dfs(u) 时标记为访问中,只有当所有后继都确认无环后,才把 u 标记为已完成。
python
def has_directed_cycle(n, edges):
graph = [[] for _ in range(n)]
for u, v in edges:
graph[u].append(v)
state = [0] * n
def dfs(u):
state[u] = 1
for v in graph[u]:
# 指向当前递归路径中的节点,说明出现回边
if state[v] == 1:
return True
if state[v] == 0 and dfs(v):
return True
state[u] = 2
return False
for u in range(n):
if state[u] == 0 and dfs(u):
return True
return False
acyclic_edges = [(0, 1), (1, 2), (2, 3)]
cyclic_edges = [(0, 1), (1, 2), (2, 3), (3, 1)]
print("无环图:", has_directed_cycle(4, acyclic_edges))
print("有环图:", has_directed_cycle(4, cyclic_edges))预期输出
text
无环图: False
有环图: True第二张图中,DFS 可能沿 0 -> 1 -> 2 -> 3 深入。当检查边 3 -> 1 时,节点 1 仍处于状态 1,说明它位于当前递归栈中,因此可以立即确认存在环。
容易误判的两种情况
只使用一个布尔 visited 会把“当前路径中的节点”和“以前已经搜索完成的节点”混在一起。后者可能被另一条边再次指向,但这只是多条路径汇合,不一定形成环。
还要注意,这套“遇到访问中节点即有环”的规则针对有向图。无向图中,DFS 会自然看到通向父节点的反向边;检测无向环时需要额外记录父节点,不能直接套用这里的判断。
复杂度与工程选择
每个节点只会从未访问进入访问中,再进入已完成;每条边也只在其起点展开时检查一次,所以时间复杂度是 ,邻接表、状态数组和递归栈共需要 空间。
DFS 版本适合需要在深度搜索过程中顺便判环的场景,例如分析依赖链或继续做 DFS 后序处理。对于节点非常多、链很深的图,Python 递归可能受递归深度限制;如果只需要判环或拓扑排序,Kahn 算法可以避免递归栈问题。
按自己的节奏,确认真正理解。