最稳妥是因为入度表+队列法天然兼具环检测与稳定排序：若输出长度≠n则存在环；它逐层剥离入度为0的就绪节点，避免DFS的递归不确定性，且要求邻接表存储与预统计入度以保障O(V+E)效率。
为什么用入度表 + 队列做拓扑排序最稳妥
因为这是唯一能同时满足「检测环」和「得到稳定排序结果」的线性方法。DFS虽然也能拓扑排序，但容易在回溯时漏判环，或因递归顺序导致结果不唯一；而入度表法天然按依赖强度逐层剥离节点，每轮只处理真正就绪的节点。
关键前提是：图必须用邻接表存储，且需预先统计每个节点的入度。如果用邻接矩阵或边列表，每次查入度都要遍历全部边，时间复杂度会退化到 O(V×E)。
常见错误现象：queue is empty but len(result) —— 这说明图中存在环，不是DAG。
如何构建带入度信息的邻接表
别直接手写字典套字典。用 defaultdict(list) 存邻接表，用 defaultdict(int) 或 Counter 统计入度，初始化时对所有出现过的节点都设入度为 0，避免漏节点。
立即学习“Python免费学习笔记（深入）”；
注意点：
- 输入边可能是重复的，得去重（用
set存边再转） - 孤立节点（无入边也无出边）必须显式加入邻接表和入度表，否则会被忽略
- 节点名不一定是整数，可能是字符串，所以不能靠
range(n)推断节点集合
示例初始化：
from collections import defaultdict, deque
<p>edges = [('A', 'B'), ('A', 'C'), ('B', 'D'), ('C', 'D')]
graph = defaultdict(list)
indeg = defaultdict(int)</p><h1>先确保所有节点都在 indeg 中</h1><p>for u, v in edges:
graph[u].append(v)
indeg[u] += 0 # 确保 u 存在
indeg[v] += 0 # 确保 v 存在</p><h1>再统计入度</h1><p>for u, v in edges:
indeg[v] += 1
用队列执行拓扑排序的核心逻辑
核心就是：把所有入度为 0 的节点一次性扔进队列，然后逐个弹出、删边、更新后继入度。不是“找到一个入度 0 就排一个”，而是“本轮所有可调度节点一起入队，保证同层节点顺序可预测（如按字母序预排序可得确定结果）”。
实操建议：
- 用
deque而非list模拟队列，popleft()是O(1) - 更新后继节点入度后，立刻检查是否降为 0，是则立即入队 —— 不要等下一轮扫描
- 如果要求字典序最小的拓扑序，把队列换成
heapq，入队改用heappush，出队用heappop - 别忘了最后校验：
len(result) != len(indeg)⇒ 有环
简短主循环：
q = deque([node for node in indeg if indeg[node] == 0])
result = []
<p>while q:
u = q.popleft()
result.append(u)
for v in graph[u]:
indeg[v] -= 1
if indeg[v] == 0:
q.append(v)</p><p>if len(result) != len(indeg):
raise ValueError("Cycle detected: not a DAG")
实际使用时最容易被忽略的边界情况
很多人跑通样例就以为没问题，但线上数据一来就崩。真正卡住的往往是这些：
- 节点名含空格或特殊字符（如
"user id"），没加引号导致解析失败 —— 建议统一用字符串且不依赖eval - 输入边里有自环（
(A, A)），会导致该节点入度永远 ≥1，直接卡死 - 图不连通，但用了
range(n)初始化入度，漏掉某些组件里的节点 - 修改了
indeg字典后，又拿原始键列表循环（字典键视图不会自动更新）
最稳妥的做法：从边列表推导完整节点集 nodes = set(u for u,v in edges) | set(v for u,v in edges)，再以此为准初始化所有结构。
