有向图与无向图中的环检测
使用父节点记录检测无向图中的环，并使用 DFS 颜色标记（白、灰、黑三态访问状态）检测有向图中的环。
有向图与无向图中的环检测 是 CoddyKit 上的免费 DSA Interview Prep 课时。 这是第 4 节课，共 4 节。 你可以在下方免费阅读本课时的完整内容 — 然后在浏览器中使用内置代码编辑器和全天候 AI 导师进行实践。 这是 DSA Interview Prep 学习路径的一部分，你的进度在网页和 CoddyKit 应用中同步。 DSA Interview Prep 课程共包含 4 节课。
为什么环检测很重要
图中的环是一条起点和终点为同一节点的路径。在许多算法中，环检测都至关重要：拓扑排序在含环图上会失败，依赖解析必须检测循环依赖，而 OS 调度中的死锁检测则需要在资源分配图中查找环。无向图和有向图采用的方式不同——它们需要从根本上不同的算法。
from collections import defaultdict
# Undirected cycle: A-B-C-A (triangle)
undirected = defaultdict(list)
for u, v in [('A','B'),('B','C'),('C','A')]:
undirected[u].append(v)
undirected[v].append(u)
# Directed cycle: A->B->C->A
directed = defaultdict(list)
for u, v in [('A','B'),('B','C'),('C','A')]:
directed[u].append(v) # one direction only
# Key difference:
# Undirected: edge A-B appears as both A->B and B->A
# Must track parent to distinguish cycle from back-edge to parent
print('Undirected and directed cycles need different detection')使用 DFS 检测无向图中的环
在无向图中，如果 DFS 访问到一个已经位于当前路径中的节点（而不只是访问过的节点），则存在环。难点在于：每条边都会以两个方向出现，因此当我们访问一个子节点时，它的邻居列表会包含当前节点（即父节点）。我们必须记录每个节点的父节点，避免错误地将返回父节点的边标记为环。如果遇到一个已访问且不是父节点的节点，就找到了一个环。
def has_cycle_undirected(n, edges):
from collections import defaultdict
graph = defaultdict(list)
for u, v in edges:
graph[u].append(v)
graph[v].append(u)
visited = set()
def dfs(node, parent):
visited.add(node)
for nb in graph[node]:
if nb not in visited:
if dfs(nb, node): # recurse with current as parent
return True
elif nb != parent: # visited and not parent = CYCLE
return True
return False
for node in range(n):
if node not in visited:
if dfs(node, -1): # -1 = no parent for root
return True
return False
print(has_cycle_undirected(4, [(0,1),(1,2),(2,3),(3,1)])) # True
print(has_cycle_undirected(3, [(0,1),(1,2)])) # False使用 BFS 检测无向图中的环
无向图中的 BFS 环检测同样会记录每个已访问节点的父节点。处理某个节点的邻居时，如果某个邻居已经访问过且不是当前节点的父节点，则存在环。使用字典存储父节点。这种 O(V + E) 的方法避免了递归限制问题，是大型图中首选的迭代式替代方案。
from collections import deque, defaultdict
def has_cycle_bfs_undirected(n, edges):
graph = defaultdict(list)
for u, v in edges:
graph[u].append(v)
graph[v].append(u)
visited = set()
for start in range(n):
if start in visited:
continue
visited.add(start)
parent = {start: -1}
queue = deque([start])
while queue:
node = queue.popleft()
for nb in graph[node]:
if nb not in visited:
visited.add(nb)
parent[nb] = node
queue.append(nb)
elif parent[node] != nb: # visited and not parent = CYCLE
return True
return False
print(has_cycle_bfs_undirected(4, [(0,1),(1,2),(2,0)])) # True有向图中的环：为什么跟踪父节点会失效
在有向图中，仅跟踪父节点是不够的。考虑 A→C 和 B→C：节点 C 有两个“父节点”，但并不存在环。正确的方法是使用三状态着色：白色（未访问）、灰色（位于当前 DFS 路径/栈中）和黑色（已完全处理）。如果 DFS 过程中遇到灰色节点，就存在环——这意味着我们找到了指向当前路径中某个祖先节点的回边。
# Three-state DFS coloring:
# WHITE (0): not yet visited
# GRAY (1): currently being visited (in DFS stack)
# BLACK (2): fully visited (all descendants processed)
# Why parent fails for directed graphs:
# A -> C (no cycle)
# B -> C (no cycle)
# If we DFS from A, mark C gray
# Then DFS from B finds C is gray -- but this is NOT a cycle!
# C is gray from A's path, not B's path.
# Parent tracking only works when the back-edge goes to the IMMEDIATE parent.
print('Directed graph: use 3-state coloring (white/gray/black)')使用三状态 DFS 检测有向图中的环
使用数组 state[]，其值为 0（白色/未访问）、1（灰色/位于栈中）或 2（黑色/已完成）。开始 DFS 时，在进入节点时将其标记为灰色，在退出节点时将其标记为黑色。如果 DFS 到达灰色节点，就找到了回边，因此存在环。如果到达黑色节点，说明该路径已经被完全探索且不含环，因此可以跳过。
def has_cycle_directed(n, edges):
from collections import defaultdict
graph = defaultdict(list)
for u, v in edges:
graph[u].append(v)
state = [0] * n # 0=white, 1=gray, 2=black
def dfs(node):
state[node] = 1 # mark gray (in stack)
for nb in graph[node]:
if state[nb] == 1: # gray = back edge = CYCLE
return True
if state[nb] == 0: # white = unvisited
if dfs(nb):
return True
state[node] = 2 # mark black (fully processed)
return False
for node in range(n):
if state[node] == 0:
if dfs(node):
return True
return False
print(has_cycle_directed(4, [(0,1),(1,2),(2,0),(2,3)])) # True (0->1->2->0)
print(has_cycle_directed(3, [(0,1),(1,2)])) # False课程表：DAG 中的环
课程表（LeetCode #207）要求判断在给定先修课程的情况下，是否能够完成所有课程。将课程建模为节点，将先修关系建模为有向边。当且仅当图是一个DAG（不含环）时，才能完成所有课程。使用三状态 DFS 环检测：如果发现环，返回假值；否则返回真值。
from collections import defaultdict
def can_finish(num_courses, prerequisites):
graph = defaultdict(list)
for a, b in prerequisites:
graph[b].append(a) # b is prerequisite for a: b -> a
state = [0] * num_courses
def dfs(course):
if state[course] == 1: return False # cycle!
if state[course] == 2: return True # already verified
state[course] = 1 # mark as in-progress
for next_course in graph[course]:
if not dfs(next_course):
return False
state[course] = 2 # mark as done
return True
return all(dfs(i) for i in range(num_courses) if state[i] == 0)
print(can_finish(2, [[1,0]])) # True: take 0 then 1
print(can_finish(2, [[1,0],[0,1]])) # False: circular dependency使用 Kahn 算法（BFS）检测环
有向图还可以使用Kahn 的 BFS 拓扑排序来检测环。统计所有节点的入度，将入度为 0 的节点放入队列。逐个处理这些节点：将其邻居的入度减 1，并将入度降为 0 的邻居加入队列。如果已处理节点数等于 V，则不存在环；否则存在环（未处理的节点构成环）。这种 O(V + E) 的方法直观易懂，也比三状态 DFS 更容易记忆。
from collections import defaultdict, deque
def has_cycle_kahn(n, edges):
graph = defaultdict(list)
in_degree = [0] * n
for u, v in edges:
graph[u].append(v)
in_degree[v] += 1
# Start with all zero in-degree nodes
queue = deque(i for i in range(n) if in_degree[i] == 0)
processed = 0
while queue:
node = queue.popleft()
processed += 1
for nb in graph[node]:
in_degree[nb] -= 1
if in_degree[nb] == 0:
queue.append(nb)
return processed != n # if not all processed, cycle exists
print(has_cycle_kahn(4, [(0,1),(1,2),(2,0),(2,3)])) # True
print(has_cycle_kahn(3, [(0,1),(1,2)])) # False找到环：收集环中的节点
有时您不仅需要检测环是否存在，还需要确定哪些节点属于环。在三状态 DFS 过程中发现回边时，可以沿调用栈（或路径栈）回溯，收集从祖先节点到当前节点之间的所有节点。与状态数组同时维护的路径栈会记录当前 DFS 路径，从而能够以 O(环长度) 的复杂度重建环。
def find_cycle_nodes(n, edges):
from collections import defaultdict
graph = defaultdict(list)
for u, v in edges:
graph[u].append(v)
state = [0] * n
path = [] # current DFS path
cycle = []
def dfs(node):
state[node] = 1
path.append(node)
for nb in graph[node]:
if state[nb] == 1: # back edge -> found cycle
start = path.index(nb)
cycle.extend(path[start:])
return True
if state[nb] == 0 and dfs(nb):
return True
path.pop()
state[node] = 2
return False
for i in range(n):
if state[i] == 0 and dfs(i):
break
return cycle
print(find_cycle_nodes(4, [(0,1),(1,2),(2,0),(2,3)])) # [0, 1, 2]查找最终安全状态
查找最终安全状态（LeetCode #802）要求找出最终能够到达终端节点（没有出边）且不会陷入环中的节点。如果从某个节点出发的所有路径都能到达终端节点，则该节点是“安全”的。使用三状态 DFS：黑色节点（已完成处理且未检测到环）是安全的。属于环或能够到达环的节点都不安全。
def eventual_safe_nodes(graph):
n = len(graph)
state = [0] * n # 0=unvisited, 1=visiting, 2=safe
def dfs(node):
if state[node] == 1: # currently visiting = cycle
return False
if state[node] == 2: # already verified safe
return True
state[node] = 1 # mark as visiting
for nb in graph[node]:
if not dfs(nb):
return False # leads to cycle, not safe
state[node] = 2 # mark as safe
return True
return [i for i in range(n) if dfs(i)]
# [[1,2],[2,3],[5],[0],[5],[],[]] means:
# 0->[1,2], 1->[2,3], 2->[5], 3->[0] (cycle!), 4->[5], 5->[], 6->[]
print(eventual_safe_nodes([[1,2],[2,3],[5],[0],[5],[],[]]))
# [2, 4, 5, 6]无向图中的冗余连接
冗余连接（LeetCode #684）用于找出一条边：将它加入原本无环的无向图后，会产生一个环。虽然可以使用 DFS 环检测来解决，但最简洁的方案是使用并查集（DSU）：逐条处理边；如果两个端点已经连通（属于同一分量），则当前边会产生环，这条边就是答案。DSU 的每次操作复杂度为 O(alpha(n))，实际上可视为 O(1)。
def find_redundant_connection(edges):
n = len(edges)
parent = list(range(n + 1))
rank = [0] * (n + 1)
def find(x):
if parent[x] != x:
parent[x] = find(parent[x]) # path compression
return parent[x]
def union(x, y):
px, py = find(x), find(y)
if px == py:
return False # already connected = cycle!
if rank[px] < rank[py]: px, py = py, px
parent[py] = px
if rank[px] == rank[py]: rank[px] += 1
return True
for u, v in edges:
if not union(u, v):
return [u, v] # this edge creates the cycle
return []
print(find_redundant_connection([[1,2],[1,3],[2,3]])) # [2,3]
print(find_redundant_connection([[1,2],[2,3],[3,4],[1,4],[1,5]])) # [1,4]总结：环检测策略
总结环检测工具集：对于无向图，使用带父节点跟踪的 DFS 或并查集。对于有向图，使用三状态 DFS（白色/灰色/黑色）或 Kahn 的 BFS 拓扑排序。当您逐条添加边（在线处理）时，选择并查集；当您还需要拓扑顺序时，选择 Kahn 算法；当您需要确定具体的环节点时，选择三状态 DFS。在面试中讨论环检测时，务必说明有向图与无向图之间的区别。
# Cycle detection summary:
# Graph type | Algorithm | Complexity
# ------------|----------------------|-----------
# Undirected | DFS + parent track | O(V + E)
# Undirected | Union-Find (DSU) | O(E * alpha(V))
# Directed | DFS 3-state (W/G/B) | O(V + E)
# Directed | Kahn's BFS topo sort | O(V + E)
# When to choose:
# Online (edges added one at a time): Union-Find
# Need topological order too: Kahn's BFS
# Need cycle nodes identified: 3-state DFS with path stack
# Simple existence check: any of the above
print('Always clarify directed vs undirected before coding')快速检查
测试您对本课中“数据结构与算法 — 编程面试准备”相关概念的理解。
课程回顾
本课中，您学习了：使用带父节点跟踪的 DFS 检测无向图中的环；使用白色/灰色/黑色三状态着色检测有向图中的环；用于有向图的Kahn BFS 替代方案；以及课程表、冗余连接和最终安全状态等应用。接下来，我们将深入学习动态规划基础。
常见问题解答
「有向图与无向图中的环检测」课时是免费的吗？
是的 — 「有向图与无向图中的环检测」的完整文本可在网页上免费阅读。要进行交互式练习（内置代码编辑器和全天候 AI 导师）并解锁 DSA Interview Prep 课程的其余内容，请升级到 CoddyKit PRO。 DSA Interview Prep 课程共包含 4 节课。
「有向图与无向图中的环检测」这节课中我会学到什么？
使用父节点记录检测无向图中的环，并使用 DFS 颜色标记（白、灰、黑三态访问状态）检测有向图中的环。 你通过在浏览器中直接运行的动手代码来练习 DSA Interview Prep，全天候 AI 导师会在你学习这节课的过程中回答你的问题。
学习 DSA Interview Prep 需要有经验吗？
无需任何先前经验。CoddyKit 上的 DSA Interview Prep 课程适合初学者到高级学习者，你可以从这里开始或从头开始，按照自己的节奏学习。 这是第 4 节课，共 4 节。
「有向图与无向图中的环检测」课时需要多长时间？
大多数 CoddyKit 课程大约需要 5–10 分钟。每节课都很精短且互动，所以你能稳步进步，并在网页和应用中从离开的地方继续。
我能在这节 DSA Interview Prep 课中编写并运行代码吗？
能。每节 DSA Interview Prep 课都包含内置代码编辑器，你可以在浏览器中直接编写并运行真实代码，并获得即时 AI 反馈 — 无需本地设置。
此课程中的所有课时
- 图的表示与遍历准备
- BFS：最短路径与层序遍历
- DFS：连通分量与洪水填充
- 有向图与无向图中的环检测