数据结构与算法 / 系统课时

拓扑排序与依赖关系

拓扑排序与依赖关系

当任务之间存在“必须先完成谁”的约束时,需要给出一个合法执行顺序,并及时发现循环依赖。本课使用 Kahn 算法统计入度、逐步释放任务,得到拓扑序并完成环检测。

学习目标

  • 理解入度、出度、有向无环图与拓扑序的关系
  • 使用 Kahn 算法生成任务执行顺序并检测循环依赖
  • 识别边方向、结果不唯一和并行任务等关键边界

依赖关系如何建图

本课约定有向边 A -> B 表示 A 必须先于 B。A 的出度包含这条边,B 的入度增加 1。只有入度为 0 的任务,才不存在尚未完成的前置依赖。

拓扑排序只适用于有向无环图。一个图可以有多个合法拓扑序:当多个节点同时入度为 0 时,它们之间没有直接的先后限制,可以按任意顺序处理,也可以在工程系统中并行执行。

Kahn 算法处理任务依赖

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
执行顺序: 需求评审 -> 接口设计 -> 数据库设计 -> 后端开发 -> 联调测试

复杂度与常见错误

统计入度会扫描全部节点和边,排序过程也会让每个节点入队一次、每条边处理一次,因此不考虑额外排序开销时,时间复杂度为 O(V+E)O(V+E),空间复杂度为 O(V)O(V)。

最常见的错误是把边方向写反,导致入度含义与业务依赖相反。另一个错误是只输出已处理节点,却不比较处理数量;这样遇到环时只会得到残缺结果,无法明确报告循环依赖。

按自己的节奏,确认真正理解。

目录与阅读设置

阅读设置

17

记录一个想法

拓扑排序与依赖关系

0 / 10000 · 笔记保存到账号。未提交的修改会在关闭、离开或刷新后丢失。

登录哪都通