任务调度、编译顺序、课程安排——拓扑排序是处理依赖关系的终极武器
拓扑排序（Topological Sort）是对有向无环图（DAG）的顶点的一种线性排序，使得对于每条有向边 u→v，u 在排序中出现在 v 之前。如果图中有环，则不存在拓扑排序。
from collections import defaultdict, deque
def topological_sort(n, edges):
"""Kahn 算法（BFS）
n: 顶点数, edges: [(from, to), ...]
返回: 拓扑序 or None(有环)
"""
graph = defaultdict(list)
in_degree = [0] * n
for u, v in edges:
graph[u].append(v)
in_degree[v] += 1
queue = deque([i for i in range(n) if in_degree[i] == 0])
order = []
while queue:
node = queue.popleft()
order.append(node)
for neighbor in graph[node]:
in_degree[neighbor] -= 1
if in_degree[neighbor] == 0:
queue.append(neighbor)
return order if len(order) == n else Nonelen(order) != n，说明有环。这比 DFS 检测环更简洁。面试推荐用 Kahn 算法！题目描述：你在这个学期必须选修 numCourses 门课程，记为 0 到 numCourses-1。给你一个数组 prerequisites，其中 prerequisites[i] = [ai, bi] 表示必须先修 bi 才能修 ai。判断是否可能完成所有课程。
class Solution:
def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
from collections import defaultdict, deque
graph = defaultdict(list)
in_degree = [0] * numCourses
for course, prereq in prerequisites:
graph[prereq].append(course)
in_degree[course] += 1
queue = deque([i for i in range(numCourses) if in_degree[i] == 0])
count = 0
while queue:
node = queue.popleft()
count += 1
for neighbor in graph[node]:
in_degree[neighbor] -= 1
if in_degree[neighbor] == 0:
queue.append(neighbor)
return count == numCourses时间复杂度：O(V+E) — 每个顶点和边访问一次
空间复杂度：O(V+E) — 邻接表 + 入度数组 + 队列
题目描述：在 LC 207 的基础上，返回一个有效的修课顺序。如果不可能完成，返回空数组。
order 列表。
class Solution:
def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:
from collections import defaultdict, deque
graph = defaultdict(list)
in_degree = [0] * numCourses
for course, prereq in prerequisites:
graph[prereq].append(course)
in_degree[course] += 1
queue = deque([i for i in range(numCourses) if in_degree[i] == 0])
order = []
while queue:
node = queue.popleft()
order.append(node)
for neighbor in graph[node]:
in_degree[neighbor] -= 1
if in_degree[neighbor] == 0:
queue.append(neighbor)
return order if len(order) == numCourses else []时间复杂度：O(V+E)
空间复杂度：O(V+E)
题目描述：给定一个 m x n 整数矩阵，找出最长递增路径的长度。对于每个格子，只能上下左右移动到更小的格子。
class Solution:
def longestIncreasingPath(self, matrix: List[List[int]]) -> int:
if not matrix:
return 0
rows, cols = len(matrix), len(matrix[0])
memo = {} # (r, c) → 最长路径长度
def dfs(r, c):
if (r, c) in memo:
return memo[(r, c)]
best = 1 # 至少包含自己
for dr, dc in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
nr, nc = r + dr, c + dc
if 0 <= nr < rows and 0 <= nc < cols and matrix[nr][nc] > matrix[r][c]:
best = max(best, 1 + dfs(nr, nc))
memo[(r, c)] = best
return best
return max(dfs(r, c) for r in range(rows) for c in range(cols))时间复杂度：O(m×n) — 每个格子只计算一次
空间复杂度：O(m×n) — memo + 递归栈
拓扑排序不仅限于课程安排，它在许多场景中都有应用：
拓扑排序天然具有环检测能力。如果排序后顶点数 < 原顶点数，说明有环。这比 DFS 三色标记法更直观。
# 环检测只需判断 len(order) vs n
if len(order) == n:
print("无环，可拓扑排序")
else:
print("有环，剩余节点构成环")在 DAG 上求最长路径，可以用拓扑排序 + DP。按照拓扑序依次更新 dp 值，保证依赖在前。
# DAG 上最长路径
for node in topological_order:
for neighbor in graph[node]:
dp[neighbor] = max(dp[neighbor], dp[node] + weight[node][neighbor])当多个节点入度同时为 0 时，用优先队列（最小堆）替代普通队列，可以保证字典序最小。
import heapq
heap = [i for i in range(n) if in_degree[i] == 0]
heapq.heapify(heap)
while heap:
node = heapq.heappop(heap) # 每次取最小的
for nb in graph[node]:
in_degree[nb] -= 1
if in_degree[nb] == 0:
heapq.heappush(heap, nb)