数据结构与算法 / 系统课时
拓扑排序与依赖关系
拓扑排序与依赖关系
当任务之间存在“必须先完成谁”的约束时,需要给出一个合法执行顺序,并及时发现循环依赖。本课使用 Kahn 算法统计入度、逐步释放任务,得到拓扑序并完成环检测。
学习目标
- 理解入度、出度、有向无环图与拓扑序的关系
- 使用 Kahn 算法生成任务执行顺序并检测循环依赖
- 识别边方向、结果不唯一和并行任务等关键边界
依赖关系如何建图
本课约定有向边 A -> B 表示 A 必须先于 B。A 的出度包含这条边,B 的入度增加 1。只有入度为 0 的任务,才不存在尚未完成的前置依赖。
拓扑排序只适用于有向无环图。一个图可以有多个合法拓扑序:当多个节点同时入度为 0 时,它们之间没有直接的先后限制,可以按任意顺序处理,也可以在工程系统中并行执行。

Kahn 算法执行过程
算法先统计所有节点的入度,再把入度为 0 的节点加入队列。每次取出一个节点并加入结果,相当于完成该任务;随后删除它的所有出边,让后继任务的入度减 1。
某个后继节点的入度减到 0 时,说明其前置任务已经全部完成,可以进入队列。循环结束后,若结果中的节点数少于图中节点总数,剩余节点无法被释放,说明它们位于一个或多个环中。
若业务要求结果在多次运行中保持字典序稳定,应使用最小堆而不是普通队列。普通队列只能保证合法,不能保证全局字典序最小。
主示例:生成任务顺序并检测环
python
from collections import deque
from typing import Optional
def topological_sort(
graph: dict[str, list[str]],
) -> Optional[list[str]]:
indegree = {task: 0 for task in graph}
for task, next_tasks in graph.items():
for next_task in next_tasks:
if next_task not in indegree:
raise ValueError(f"未定义的任务: {next_task}")
indegree[next_task] += 1
queue = deque(
sorted(task for task, degree in indegree.items() if degree == 0)
)
order = []
while queue:
task = queue.popleft()
order.append(task)
for next_task in sorted(graph[task]):
# 删除当前任务的出边,释放已经满足依赖的后继任务
indegree[next_task] -= 1
if indegree[next_task] == 0:
queue.append(next_task)
return order if len(order) == len(graph) else None
graph = {
"需求评审": ["接口设计", "数据库设计"],
"接口设计": ["后端开发"],
"数据库设计": ["后端开发"],
"后端开发": ["联调测试"],
"联调测试": [],
}
order = topological_sort(graph)
if order is None:
print("存在循环依赖")
else:
print("执行顺序:", " -> ".join(order))预期输出:
text
执行顺序: 需求评审 -> 接口设计 -> 数据库设计 -> 后端开发 -> 联调测试复杂度与常见错误
统计入度会扫描全部节点和边,排序过程也会让每个节点入队一次、每条边处理一次,因此不考虑额外排序开销时,时间复杂度为 ,空间复杂度为 。
最常见的错误是把边方向写反,导致入度含义与业务依赖相反。另一个错误是只输出已处理节点,却不比较处理数量;这样遇到环时只会得到残缺结果,无法明确报告循环依赖。
按自己的节奏,确认真正理解。