一文搞懂拓扑排序：任务依赖与课程先修实战

为什么需要拓扑排序：从依赖冲突说起

在真实系统中，很多任务并不是“想执行就执行”。编译一个前端项目时，必须先安装依赖、再生成类型声明、最后打包；部署后端服务时，要先初始化数据库，再执行迁移，最后启动应用。学校课程也类似：不修完数据结构，通常不能学习算法设计；不修完离散数学，学习图论时会比较吃力。

这类问题的共同特征是：任务之间存在有向依赖，我们需要求出一个满足所有先后约束的执行顺序。这正是 topological-sort（拓扑排序）解决的问题。

拓扑排序只适用于有向无环图（DAG，Directed Acyclic Graph）。图中的每个节点表示一个任务或课程，有向边 A -> B 表示 A 必须在 B 之前完成。如果图中存在环，例如 A 依赖 B、B 依赖 C、C 又依赖 A，那么任何任务都无法最先开始，拓扑排序不存在。

下面先用一张图展示“入度为零的任务进入队列、执行后解除下游依赖”的核心过程。

方案对比：Kahn 算法与 DFS 后序反转

拓扑排序常见实现有两种，面试和工程中都应掌握。

Kahn 算法：基于入度的广度优先思路

Kahn 算法的核心是维护每个节点的入度。入度表示还有多少前置任务没有完成。算法步骤如下：

1. 建立邻接表，并统计每个节点的入度；
2. 将所有入度为 0 的节点放入队列；
3. 每次取出一个节点，加入结果序列；
4. 遍历它的邻接节点，将这些节点的入度减 1；
5. 某个邻接节点入度变成 0 时，将其入队；
6. 如果结果长度不等于节点数，说明存在环。

这种方法直观、稳定，并且天然适合任务调度系统。使用普通队列时，得到的是一种合法顺序；如果希望每次优先执行编号最小或优先级最高的任务，可以把队列替换为小根堆。

DFS 方案：基于后序遍历的逆序

深度优先搜索也可以求拓扑序。对每个未访问节点进行 DFS，当一个节点的所有后继都处理完成后，把它追加到后序列表中，最后将列表反转。

为什么要反转？因为边 A -> B 表示 A 必须在 B 前面，而 DFS 完成顺序通常是先完成 B、再完成 A，后序列表为 [B, A]，反转后才得到 [A, B]。

DFS 实现需要三种访问状态：

• 0：未访问；
• 1：正在访问，位于当前递归路径上；
• 2：已经处理完成。

如果 DFS 中遇到状态为 1 的节点，说明当前路径再次经过了一个尚未完成的节点，即存在环。

两种方案的时间复杂度均为 O(V + E)，空间复杂度为 O(V + E)，其中 V 是节点数，E 是边数。Kahn 算法更容易解释调度过程，也便于非递归实现；DFS 代码较短，但递归深度过大时可能触发 Python 递归栈限制。

Python 实战：课程先修关系求学习顺序

LeetCode《课程表 II》是拓扑排序的经典题：给定课程总数 numCourses，以及先修关系数组 prerequisites，其中 prerequisites[i] = [a, b] 表示必须先完成课程 b，才能学习课程 a。要求返回任意一种合法课程顺序；若无法完成全部课程，返回空数组。

下面使用 Kahn 算法实现。

from collections import deque
from typing import List


def find_order(num_courses: int, prerequisites: List[List[int]]) -> List[int]:
    """返回满足先修关系的课程顺序；存在环时返回空列表。"""
    # graph[b] 保存所有必须在 b 之后学习的课程
    graph = [[] for _ in range(num_courses)]
    indegree = [0] * num_courses

    for course, prerequisite in prerequisites:
        graph[prerequisite].append(course)
        indegree[course] += 1

    # 所有没有先修课的课程都可以最先学习
    queue = deque([
        course_id
        for course_id in range(num_courses)
        if indegree[course_id] == 0
    ])

    order = []

    while queue:
        current = queue.popleft()
        order.append(current)

        # 当前课程完成后，解除它对后续课程的一个约束
        for nxt in graph[current]:
            indegree[nxt] -= 1
            if indegree[nxt] == 0:
                queue.append(nxt)

    # 只要有课程没有进入结果，就说明这些课程处于环中
    return order if len(order) == num_courses else []


# 示例：课程 0 依赖课程 1，课程 2 依赖课程 0
# 合法顺序之一是 [1, 0, 2]
print(find_order(3, [[0, 1], [2, 0]]))

# 存在环：0 依赖 1，1 依赖 0，无法完成
print(find_order(2, [[0, 1], [1, 0]]))

代码为什么能检测环

在有向无环图中，一定至少存在一个入度为 0 的节点。每完成一个节点，就相当于删除它和它的出边；这个过程会不断释放新的可执行节点，最终所有节点都会进入结果。

如果存在环，环上的每个节点至少都有一个来自环内的入边。即使环外节点全部执行完，环上节点的入度也不可能降到 0，因此它们永远不会入队。最终 len(order) < num_courses，据此即可判断依赖关系非法。

工程改造：从课程表到构建系统任务调度

课程编号是连续整数，但真实构建系统中的任务通常有名称，例如 install、generate-types、test、build。这时可以用字典保存邻接表和入度，使算法支持字符串任务。

from collections import deque


def schedule_tasks(tasks, dependencies):
    """
    tasks: 全部任务名称列表
    dependencies: [(pre, task)]，表示 pre 必须先于 task 执行
    返回可执行顺序；如果存在循环依赖则抛出异常。
    """
    graph = {task: [] for task in tasks}
    indegree = {task: 0 for task in tasks}

    for pre, task in dependencies:
        # 防御未知任务，避免调度时出现隐式节点
        if pre not in graph or task not in graph:
            raise ValueError(f"未知任务: {pre} -> {task}")
        graph[pre].append(task)
        indegree[task] += 1

    queue = deque([
        task for task in tasks
        if indegree[task] == 0
    ])
    result = []

    while queue:
        current = queue.popleft()
        result.append(current)

        for nxt in graph[current]:
            indegree[nxt] -= 1
            if indegree[nxt] == 0:
                queue.append(nxt)

    if len(result) != len(tasks):
        remaining = [task for task in tasks if task not in result]
        raise ValueError(f"检测到循环依赖，涉及任务: {remaining}")

    return result


tasks = ["install", "generate-types", "test", "build", "deploy"]
dependencies = [
    ("install", "generate-types"),
    ("install", "test"),
    ("generate-types", "build"),
    ("test", "build"),
    ("build", "deploy"),
]

print(" -> ".join(schedule_tasks(tasks, dependencies)))

这段代码可以直接用于简单的流水线编排。若多个任务之间没有依赖关系，它们在拓扑序中的相对位置可能不固定。例如 generate-types 和 test 都只依赖 install，谁先执行都合法。若业务要求固定顺序，应显式增加依赖边，而不是依赖队列的偶然行为。

复杂度分析与适用边界

设任务数为 V，依赖边数为 E：

• 建图需要遍历所有任务和依赖，时间为 O(V + E)；
• 每个节点最多入队一次、出队一次；
• 每条有向边最多被检查一次；
• 邻接表占用 O(V + E) 空间，队列和结果数组占用 O(V) 空间。

因此总体时间复杂度为 O(V + E)，空间复杂度为 O(V + E)。这使得拓扑排序能够扩展到大规模模块依赖图和任务 DAG。

但要注意，拓扑排序只负责满足先后约束，并不自动解决资源竞争、失败重试、并行度控制等调度问题。如果要在多核机器上并行执行任务，需要在每一批入度为 0 的任务中结合线程池或协程池调度，并在任务失败后决定取消下游还是继续其他分支。

避坑总结：拓扑排序的高频错误

1. 边的方向建反，导致先修课变成后续课

常见错误是看到 [0, 1] 表示“0 依赖 1”，却建成 0 -> 1。这会让算法认为 0 必须在 1 前面，与题意完全相反。修正方法是明确语义：若 b 是 a 的前置条件，就应添加边 b -> a，并让 indegree[a] += 1。建图后最好用一个两节点样例检查输出顺序。

2. 只判断队列是否为空，忘记比较结果长度

很多初学者在队列清空后直接返回结果，但环上的节点根本不会入队，此时返回的是一个“部分顺序”，并不是合法完整答案。正确做法是执行结束后检查 len(result) == num_courses。在工程代码中，还应把未完成节点或疑似环路径输出到日志，方便定位循环依赖。

3. DFS 只用布尔访问标记，无法正确识别回溯边

如果只用 visited = set()，已经访问过的节点无法区分“在当前递归路径上”还是“之前完整处理过”。例如多个分支汇聚到同一个公共后继时，普通访问标记可能误判为环。修正方法是使用白、灰、黑三种状态：灰色节点代表当前 DFS 路径上的节点，再次遇到灰色节点才说明存在环。

4. 重复依赖没有去重，导致入度被重复增加

在配置系统中，同一条依赖可能因为配置合并而出现多次。如果重复执行 indegree[task] += 1，但邻接边也被重复遍历，通常仍可能得到结果；若只重复记录入度、没有重复边，任务可能永远无法降到入度 0。更稳妥的方式是在建模阶段使用集合去重，或在读取配置时校验重复边。

5. 把拓扑序当成唯一答案，忽略无关节点的任意性

只要多个节点同时入度为 0，它们之间就没有强制先后关系，因此拓扑排序结果通常不唯一。测试时不要只断言一个固定数组，而应验证两个条件：结果包含全部节点；每一条依赖边的前置任务都出现在后继任务之前。

掌握“建图、统计入度、释放零入度节点、环检测”这条主线后，拓扑排序不仅能解决课程先修题，也能落地到构建系统、数据流水线、SQL 任务编排和微服务发布顺序等实际场景。

免责声明

本工具与文章内容仅用于学习测试场景，优化建议仅供参考，请勿直接用于生产环境，由此产生的风险自行承担。