如何在Python中构建有向无环图DAG并进行拓扑排序_使用入度表和队列实现-Python教程-PHP中文网

最稳妥是因为入度表+队列法天然兼具环检测与稳定排序：若输出长度≠n则存在环；它逐层剥离入度为0的就绪节点，避免dfs的递归不确定性，且要求邻接表存储与预统计入度以保障o(v+e)效率。

如何在python中构建有向无环图dag并进行拓扑排序_使用入度表和队列实现

为什么用入度表 + 队列做拓扑排序最稳妥

因为这是唯一能同时满足「检测环」和「得到稳定排序结果」的线性方法。DFS虽然也能拓扑排序，但容易在回溯时漏判环，或因递归顺序导致结果不唯一；而入度表法天然按依赖强度逐层剥离节点，每轮只处理真正就绪的节点。

关键前提是：图必须用邻接表存储，且需预先统计每个节点的入度。如果用邻接矩阵或边列表，每次查入度都要遍历全部边，时间复杂度会退化到 O(V×E)。

常见错误现象：queue is empty but len(result) —— 这说明图中存在环，不是DAG。

如何构建带入度信息的邻接表

别直接手写字典套字典。用 defaultdict(list) 存邻接表，用 defaultdict(int) 或 Counter 统计入度，初始化时对所有出现过的节点都设入度为 0，避免漏节点。

注意点：

输入边可能是重复的，得去重（用 set 存边再转）
孤立节点（无入边也无出边）必须显式加入邻接表和入度表，否则会被忽略
节点名不一定是整数，可能是字符串，所以不能靠 range(n) 推断节点集合

示例初始化：

python-parallelization

将顺序 Python 代码转换为并行/并发实现，用于在需要并行化 Python 代码、提升性能时使用。

下载

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
</p>

用队列执行拓扑排序的核心逻辑

核心就是：把所有入度为 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")
</p>