拓扑排序 学习笔记
学习日期： 2026-05-12
前置知识： BFS + 队列 + 入度概念
问题场景
有 n 门课，每门课有先修要求。请排出上课顺序，让每门课的预修课都在前面。
微积分(1) → 线代(2) → 概率论(4)↓ ↓高数(3) ───────────→ 机器学习(6)↑计概(5)
核心思想
入度 = 被几条边指着。
入度为 0 的点 → 没有前置依赖 → 可以直接上
完整过程图解
初始:课: 1 2 3 4 5 6入度: 0 1 1 1 0 2入度为0 → 1和5 → 入队━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━第1步: q = [1, 5]弹出 1: 删掉 1→2, 1→32的入度 1→0 ✓ 入队3的入度 1→0 ✓ 入队弹出 5: 删掉 5→66的入度 2→1order = [1, 5]q = [2, 3]入度: 0 0 0 1 0 1━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━第2步: q = [2, 3]弹出 2: 删掉 2→44的入度 1→0 ✓ 入队弹出 3: 删掉 3→66的入度 1→0 ✓ 入队order = [1, 5, 2, 3]q = [4, 6]━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━第3步: q = [4, 6]弹出 4: 删掉 4→6（6入度已经是0，不变）弹出 6: 无出边order = [1, 5, 2, 3, 4, 6]q = []len(order) = 6 == n → 排序成功 ✓━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━结果: 1 5 2 3 4 6 (多种答案均可)验证每条边是否从左指向右:1→2 ✓ 1→3 ✓ 2→4 ✓ 3→6 ✓ 4→6 ✓ 5→6 ✓
环检测
若存在环，如 2→4 且 4→2：初始: 2入度=1, 4入度=1第1步处理后: 2入度=1, 4入度=1 ← 永远≥1环上的点永远进不了队列！q 为空 → while 退出 → len(order) < n → 有环
不会死循环。 队列为空自动退出，不会无限跑。
模板代码
from collections import dequen, m = map(int, input().split())g = [[] for _ in range(n + 1)]
indeg = [0] * (n + 1) # 入度数组for _ in range(m):u, v = map(int, input().split()) # u → vg[u].append(v)indeg[v] += 1# 入度为0的点入队
q = deque([i for i in range(1, n + 1) if indeg[i] == 0])
order = []while q:u = q.popleft() # 弹出队首order.append(u) # 加入结果for v in g[u]: # 删除出边indeg[v] -= 1if indeg[v] == 0: # 入度归零则入队q.append(v)# 判断
if len(order) < n:print("有环，无法拓扑排序")
else:print(*order)
关键要点
| 要点 | 说明 |
|---|---|
| 入度 | 一个点被几条边指着 |
| 入队条件 | 入度为 0 |
| 删边 | 遍历 u 的邻居，入度减 1 |
| 环检测 | len(order) < n 说明有环 |
| 多种答案 | 入度为 0 的点顺序任意，全正确 |
| 复杂度 | O(n + m) |