拓扑排序详解：附代码

Mohammed Islam Hadjoudj

Expert Operations Research Engineer

什么是拓扑排序？

拓扑排序是有向无环图（DAG）节点的一个线性排序，使得对每一条从 u 到 v 的有向边，节点 u 都排在节点 v 之前。通俗地说：把一切排成一行，让每个箭头都指向前方。

这个定义里内置了两个条件。图必须是有向的（依赖有方向：A 在 B 前和 B 在 A 前并不相同），且是无环的（没有环）。如果 A 必须在 B 前、B 又必须在 A 前，就不可能存在有效的顺序。树和 DAG 在这里是近亲；关于树的一面，见有根树。

你何时需要它

每当一个问题听起来像"按尊重前置条件的顺序做这些事"时，拓扑排序就是答案。你可以通过这些信号认出它：

• 依赖："任务 X 要求先完成任务 Y。"
• 排序或调度："我该以什么顺序修这些课？"
• 构建与编译："按顺序编译模块，使每个 import 都已存在。"
• 解析："安装包时，让每个依赖都先于需要它的东西被安装。"

它是技术面试中最常见的套路之一，因此出现在编程面试图算法指南中，也构成图论学习路线图的一个阶段。

Kahn 算法，分步讲解

最直观的方法是 Kahn 算法。它依赖每个节点的一个数字：入度，即入边的数量。入度为 0 的节点没有未满足的前置条件，因此可以安全地接下来放置它。

循环很简单：取任意入度为 0 的节点，输出它，并移除它的出边，这会降低其邻居的入度。重复直到什么都不剩。让我们在这个 DAG 上运行它。每个节点都标注了它在某个有效顺序中的位置。

下面是执行过程。队列保存入度已降到 0 的节点。我们从 A 开始，它是唯一不依赖任何东西的节点。

注意，取走 A 之后，B 和 C 的入度同时降到了 0。两者都可以接下来出场，这正是为什么一个 DAG 通常有许多有效顺序。在实时图上看入度下降会让它豁然开朗，你可以在算法可视化工具中试一试。

Python 实现

Kahn 算法几乎可以直接翻译成代码。我们计算每个入度，用入度为零的节点初始化一个队列，然后把它清空。

from collections import deque, defaultdict

def topological_sort(num_nodes, edges):
    graph = defaultdict(list)
    in_degree = [0] * num_nodes

    for u, v in edges:          # 边 u -> v 表示 u 在 v 之前
        graph[u].append(v)
        in_degree[v] += 1

    # 用每个没有前置条件的节点初始化。
    queue = deque(n for n in range(num_nodes) if in_degree[n] == 0)
    order = []

    while queue:
        node = queue.popleft()
        order.append(node)
        for neighbour in graph[node]:
            in_degree[neighbour] -= 1        # 移除这条边
            if in_degree[neighbour] == 0:    # 不再有前置条件
                queue.append(neighbour)

    # 若某个节点始终没到达入度 0，是环把它挡住了。
    if len(order) == num_nodes:
        return order
    return []   # 检测到环，没有有效顺序

最后的检查是最优雅的部分：如果输出里缺了任何节点，那些节点就被困在一个环里。所以，同一段给 DAG 排序的代码，也检测出这个图究竟是不是 DAG。

DFS 方法

还有第二种基于深度优先搜索的经典方法。运行 DFS，当一个节点完成（它的所有后代都已探索）时，把它压入一个栈。拓扑排序就是把这个栈倒着读。

直觉是：一个节点只有在它所指向的一切都完成之后才会完成，因此在完成的逆序中，它排在它所有后代之前。DFS 版本无需记录入度，但你仍必须通过跟踪当前递归路径上的节点来防范环。两种方法同样有效；Kahn 的通常更容易推理，而 DFS 更紧凑。

环，以及它们为何让它失效

拓扑排序存在当且仅当图是无环的。原因立竿见影：环 A → B → A 要求 A 在 B 前、B 又在 A 前，同时成立，这在一条直线上是不可能的。

有用的推论：拓扑排序同时也是一个环检测器。在 Kahn 算法中，如果你无法输出全部 V 个节点，剩下的节点就构成至少一个环。在 DFS 版本中，遇到一个已经在当前路径上的节点，就意味着有环。

这就是为什么"课程表（Course Schedule）"类型的面试题，其实在问"这到底可不可能？"，要用拓扑排序来解。

复杂度

两种算法都是最优的：它们对每个节点和每条边都恰好触碰一次。

正是这种线性开销，让拓扑排序能扩展到巨大的依赖图。要看它与其他所有图算法的对比，见复杂度指南和一页纸的速查表。

现实应用

• 构建系统：Make、Bazel 等对目标做拓扑排序，让依赖先构建。
• 包管理器：npm、pip 和 apt 从依赖 DAG 推导安装顺序。
• 任务与作业调度：电子表格重算单元格、CI 流水线排定阶段、排课工具。
• 编译器：排定声明顺序并求值表达式，使每个符号在使用前都已定义。