Python拓扑排序实现：入度表与队列解课安排

本文深入剖析了Python中拓扑排序在课程安排问题中的高效实现要点，重点强调使用collections.deque替代list.pop(0)以避免O(n)队首弹出导致的超时陷阱，并厘清建图方向（先修课→后续课）、入度数组正确初始化、孤立节点处理、环检测的本质逻辑（通过拓扑序列长度是否等于n判断）等极易出错的核心细节；文章直击90% WA和TLE的根源——非语法性语义与边界逻辑错误，辅以典型反例（如自环、最小环[[1,0],[0,1]]）和工程建议（编号连续优先用列表建图），为算法新手和刷题者提供兼具深度与实操性的避坑指南。

拓扑排序用 collections.deque 而不是 list.pop(0)

因为课程安排问题本质是 BFS 模拟，要频繁从队首取节点（入度为 0 的课程），list.pop(0) 是 O(n) 操作，会把整体复杂度拖到 O(V²)，而 deque.popleft() 是 O(1)。

常见错误现象：Time Limit Exceeded 在大规模课程数（比如 10⁵）时突然出现，但小样例全过——大概率是用了 list 模拟队列。

• 初始化队列必须只放入度为 0 的节点，不能漏（比如没有前置课的课程）
• 每次从队列取出一个节点后，要遍历它所有邻接节点（即它作为先修课的后续课程），对每个邻接节点入度减 1
• 入度减到 0 的邻接节点才进队，不能提前塞进去

graph 建图用字典还是列表？看课程编号是否连续

如果课程编号是 0 到 n-1 的整数，直接用 graph = [[] for _ in range(n)]；如果编号稀疏（比如 [1, 3, 7, 100]），就用 defaultdict(list) 或普通 dict。

性能影响：用列表建图快、内存紧凑；用字典更灵活但有哈希开销。课程安排题一般编号连续，别绕弯子。

• 建图时别把边方向搞反——[a, b] 表示 “a 是 b 的先修课”，所以应加边 a → b，即 graph[a].append(b)
• 入度数组长度必须和节点总数一致，否则下标越界。用 indeg = [0] * n 最稳妥

怎么判断有没有环？靠拓扑序列长度

拓扑排序本身不显式检测环，而是通过最终结果长度来判断：如果输出的排序长度 != n，说明有节点始终无法入队（入度一直 > 0），即存在环。

错误写法：单独写 DFS 判环再跑拓扑——多一遍遍历，没必要；Kahn 算法天然带环检测能力。

• 不要在循环里提前 return False，等队列空了再比长度
• 注意题目是否要求返回具体环（比如输出冲突课程），这时标准 Kahn 不够，得换 DFS + 状态数组
• 有些题输入含自环（[x, x]），建图时就要过滤，否则 indeg[x] 先加 1 再减 1，看似归零实则漏判

Python 实现里最容易错的三个细节

不是语法错，是语义和边界逻辑错——90% 的 WA 都出在这儿。

• 输入 prerequisites 为空时，n 可能大于 0，此时所有课程都无依赖，结果必须是 list(range(n))，不能直接返回空列表
• indeg 数组初始化后，必须对每个 prerequisites 中的 b 执行 indeg[b] += 1，漏掉任何一条边都会导致错误入度
• 队列初始装入节点时，要用 for i in range(n): if indeg[i] == 0: q.append(i)，不能只遍历 prerequisites 里出现过的节点——没出现在边里的节点（孤立课程）也得进队

环检测和入度更新是绑在一起的动作，拆开会出事。写完别急着交，拿 n=2, prerequisites=[[1,0],[0,1]] 这种最小环测一下。

理论要掌握，实操不能落！以上关于《Python拓扑排序实现：入度表与队列解课安排》的详细介绍，大家都掌握了吧！如果想要继续提升自己的能力，那么就来关注golang学习网公众号吧！