引言 (Introduction)
有向无环图（Directed Acyclic Graph, DAG）是图论中一个特殊的子类：边有方向，且不存在环。DAG 的重要性在于——现实世界中大量依赖关系天然是无环的（编译顺序、任务调度、课程先修），而拓扑排序正是处理这些依赖关系的核心算法。
本文是本系列第四篇。在掌握了图遍历和最短路径算法后，我们将聚焦于拓扑排序的两种实现方法，以及 DAG 上的 DP 建模。拓扑排序不仅是图论的基础操作，也是 DP 中「无后效性」的图论表达。
1. 拓扑排序的定义
给定一个 DAG，拓扑排序给出节点的线性排列，使得对于每条有向边 $(u, v)$，$u$ 在排列中出现在 $v$ 之前。
等价地说，拓扑排序将图中所有节点排成一行，所有边都从左指向右。
1 → 2 → 4
\ /
→ 3 →
可能的拓扑序：[1, 2, 3, 4] 或 [1, 3, 2, 4]
拓扑排序存在的充要条件：图是 DAG（无环）。如果图中存在环，拓扑序必不存在（环中的节点互相依赖，无法线性排列）。
2. Kahn 算法（入度表 + BFS）
2.1 核心思想
- 统计每个节点的入度（in-degree）。
- 将所有入度为 0 的节点入队（无依赖，可以立即执行）。
- 依次出队，将出队节点的所有后继的入度减 1；若减到 0 则入队。
- 若最终出队节点数 $\neq V$，说明图中存在环。
2.2 完整代码
from typing import List, Dict
from collections import deque
def kahn_topological_sort(n: int, edges: List[List[int]]) -> List[int]:
"""
n: 节点数（0..n-1）
edges: [[u, v], ...] 表示 u → v
返回: 拓扑序列；若不合法（有环）则返回空列表
"""
graph: Dict[int, List[int]] = {i: [] for i in range(n)}
indegree: List[int] = [0] * n
for u, v in edges:
graph[u].append(v)
indegree[v] += 1
queue: deque[int] = deque([i for i in range(n) if indegree[i] == 0])
order: List[int] = []
while queue:
u = queue.popleft()
order.append(u)
for v in graph[u]:
indegree[v] -= 1
if indegree[v] == 0:
queue.append(v)
return order if len(order) == n else [] # 长度不足 → 有环
复杂度：时间 $O(V + E)$，空间 $O(V + E)$。
2.3 为什么 BFS 能够生成拓扑序？
入度为 0 的节点是所有依赖已满足的节点——它们不依赖任何其他节点，可以立即排入序列。当一个节点出队后，它施加于后继节点的依赖关系被解除（入度 -1）。BFS 的层序天然保证了所有指向 $v$ 的节点都在 $v$ 之前出队。
3. DFS 后序遍历法
3.1 算法思想
对图进行 DFS。节点完成 DFS（所有邻居已处理完毕）时将其加入结果列表。最后将结果列表反转，即得到拓扑序。
直觉：在 DFS 的后序中，一个节点的所有后继必在它之前被输出（因为它们在递归栈的更下层）。反转后，所有后继排在它之后 → 拓扑序。
3.2 完整代码
from typing import List, Dict
def dfs_topological_sort(n: int, edges: List[List[int]]) -> List[int]:
graph: Dict[int, List[int]] = {i: [] for i in range(n)}
for u, v in edges:
graph[u].append(v)
visited: List[int] = [0] * n # 0=未访问, 1=访问中, 2=已完成
order: List[int] = []
has_cycle = False
def dfs(u: int) -> None:
nonlocal has_cycle
visited[u] = 1 # 标记为「访问中」
for v in graph[u]:
if visited[v] == 0:
dfs(v)
elif visited[v] == 1: # 回边 → 发现环
has_cycle = True
visited[u] = 2 # 标记为「已完成」
order.append(u) # 后序加入
for u in range(n):
if visited[u] == 0:
dfs(u)
if has_cycle:
return []
order.reverse() # 反转得到拓扑序
return order
复杂度：时间 $O(V + E)$，空间 $O(V)$。
三色标记法：
0（白）：未访问。1（灰）：递归栈中（当前正在处理）。2（黑）：处理完成。
若在 DFS 中遇到灰色节点（仍在递归栈中）→ 发现回边 → 存在环。
3.3 BFS vs DFS 拓扑排序
| Kahn (BFS) | DFS 后序 | |
|---|---|---|
| 思路 | 不断剥离入度为 0 的节点 | 深度优先，后序反转 |
| 环检测 | 输出长度 ≠ V | 三色标记法（遇灰即环） |
| 输出唯一性 | 同一层可能有多种出队顺序 | 同一层可能有多种 DFS 顺序 |
| 适合场景 | 需要按层分组（如课程学期安排） | 需要递归视角（如在 DFS 树上做 DP） |
拓扑序不唯一：只要图不是「全序」（即不是一条线性的链），拓扑序就有多种。两种方法都可能生成不同的合法拓扑序——这取决于图的遍历顺序，而非算法的正误。
4. LeetCode 207：课程表
题目：numCourses 门课程，prerequisites[i] = [a, b] 表示要先修 $b$ 才能修 $a$。判断能否完成所有课程（即图是否为 DAG）。
这是拓扑排序的判定问题——输出是否为 True 等价于「图中无环」。
from typing import List
from collections import deque
class Solution:
def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
graph = {i: [] for i in range(numCourses)}
indegree = [0] * numCourses
for a, b in prerequisites:
graph[b].append(a)
indegree[a] += 1
q = deque([i for i in range(numCourses) if indegree[i] == 0])
taken = 0
while q:
u = q.popleft()
taken += 1
for v in graph[u]:
indegree[v] -= 1
if indegree[v] == 0:
q.append(v)
return taken == numCourses
复杂度：时间 $O(V + E)$，空间 $O(V + E)$。
建图方向：prerequisites[i] = [a, b] 表示 $b \to a$（先学 $b$ 才能学 $a$）。建图时 graph[b].append(a) 符合「$b$ 完成后 $a$ 的依赖被解除」。
5. LeetCode 210：课程表 II
题目：207 的升级版——返回任意一个合法的上课顺序。若无法完成则返回空数组。
只需在 207 的基础上将出队顺序记录下来即可。
from typing import List
from collections import deque
class Solution:
def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:
graph = {i: [] for i in range(numCourses)}
indegree = [0] * numCourses
for a, b in prerequisites:
graph[b].append(a)
indegree[a] += 1
q = deque([i for i in range(numCourses) if indegree[i] == 0])
order = []
while q:
u = q.popleft()
order.append(u)
for v in graph[u]:
indegree[v] -= 1
if indegree[v] == 0:
q.append(v)
return order if len(order) == numCourses else []
6. LeetCode 802：找到最终的安全状态
题目：有向图中，一个节点是「安全」的当且仅当从它出发的所有路径最终都到达终点（出度为 0 的节点，即终端节点）。找出所有安全节点。
6.1 逆向拓扑排序
这道题的关键在于反向建图：如果 $u$ 的所有后继都是安全的，那么 $u$ 也是安全的。这等价于「出度为 0 的节点（终端）→ 不断剥离安全节点」——是拓扑排序的逆向版本。
具体做法：
- 反向建图（将原图的边方向反转）。
- 统计原图中每个节点的出度。
- 从出度为 0 的终端节点开始，对反向图做拓扑排序（不断将「出度为 0」的节点标记为安全）。
from typing import List
from collections import deque
class Solution:
def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:
n = len(graph)
# 反向图: v → u（原图中 u → v）
reverse: List[List[int]] = [[] for _ in range(n)]
outdegree: List[int] = [0] * n
for u in range(n):
outdegree[u] = len(graph[u])
for v in graph[u]:
reverse[v].append(u)
# 从原图出度为 0 的节点开始（终端节点）
q: deque[int] = deque([i for i in range(n) if outdegree[i] == 0])
safe: List[int] = []
while q:
v = q.popleft()
safe.append(v)
for u in reverse[v]: # 考察所有指向 v 的节点 u
outdegree[u] -= 1
if outdegree[u] == 0: # u 的所有后继都是安全的
q.append(u)
return sorted(safe)
复杂度：时间 $O(V + E)$，空间 $O(V + E)$。
建模要点：逆向拓扑排序的精髓在于「反向建图 + 出度表」。正向拓扑排序是从「入度为 0（无人依赖）」开始剥离，逆向拓扑排序是从「出度为 0（无需再往后走）」开始剥离。两者共享同一套框架，只是方向和语义不同。
7. DAG 与 DP 的关系
DAG 是 DP 的天然载体。DP 要求状态转移无后效性——一旦确定了计算顺序，前面的状态不依赖后面的状态。拓扑排序恰好提供了这个顺序。
在 DAG 上做 DP 的通用模板：
from typing import List, Dict
from collections import deque
def dag_dp(n: int, edges: List[List[int]], values: List[int]) -> int:
"""在 DAG 上 DP 求最长路径的节点权值和"""
graph: Dict[int, List[int]] = {i: [] for i in range(n)}
indegree: List[int] = [0] * n
for u, v in edges:
graph[u].append(v)
indegree[v] += 1
# 拓扑排序
q = deque([i for i in range(n) if indegree[i] == 0])
dp: List[int] = values[:] # dp[i] = 以 i 结尾的最大权值和
ans = max(dp) if dp else 0
while q:
u = q.popleft()
for v in graph[u]:
dp[v] = max(dp[v], dp[u] + values[v])
indegree[v] -= 1
if indegree[v] == 0:
q.append(v)
ans = max(ans, dp[v])
return ans
在 DAG 上做 DP 的复杂度与拓扑排序一致——$O(V + E)$，比在一般图上做 DP 高效（后者可能需要多次迭代直到收敛，如 Bellman-Ford 的 $O(VE)$）。
结论 (Conclusion)
本文完成了拓扑排序与 DAG 的系统性学习：
- Kahn 算法（BFS + 入度表）：不断剥离入度为 0 的节点，出队序列即为拓扑序。是最常用的实现。
- DFS 后序法：后序遍历 + 反转，三色标记法检测环。提供了递归视角。
- 逆向拓扑排序（802）：反向建图 + 出度表，从「终点」向前剥离。
三道题目（207、210、802）覆盖了环检测、顺序输出、安全状态判定三种经典模式。DAG 上的 DP 模板则将拓扑排序与 DP 系列的建模思想贯通了起来。
下一篇预览：本系列的收官之作——二分图判定（染色法）、Tarjan 算法求桥与割点、带权并查集（LeetCode 785、1192、399），以及全系列复盘对照表。