拓扑排序：行军次序的调度表

拓扑排序：行军次序的调度表

「topological order」，拓扑序——这个行话在构建系统与任务编排的圈子里天天挂嘴边，它要解决的问题是：一张布满依赖关系的任务清单，如何排出一条不违反任何依赖的执行次序。侦察未毕不可定案、粮草未齐不可开拔、定案未下不可行军——远征队的参谋部把这类约束画成有向图（任务为顶点、依赖为边），拓扑排序负责把图压平成一张合法的行军次序表。本章收官之战由它担纲：它不来自第 4 章的缩点骨架，却与那套强连通思想严密衔接——有环则无解，缩点可救场。

问题的形态与存在性

形式化定义很干脆：对有向图的顶点排一个全序，使得每条有向边 u→v 都满足"u 排在 v 前"。这样的序叫拓扑序，能排出拓扑序的图必是有向无环图（DAG）。

两个方向的存在性论证都值得亲手过一遍。必要性一目了然：若图有环，环上的顶点互相"依赖对方先行"，任何线性次序都无法让环里每条边都指向后方。充分性的证明则藏着一个算法：无环图必存在入度为零的顶点（反证：若人人有入边，沿入边逆行必然撞环）；把它摘掉放在序列最前，剩下的小图依旧无环，归纳下去全体摘完，摘的次序就是拓扑序。存在性证明与算法构造在这里合二为一——这种"证明即程序"的风格是本册反复提倡的思维习惯。

还要澄清两个常见误会。其一，拓扑序通常不唯一：互不依赖的任务可以任意穿插，两个不同的序可能同样合法——这解释了为什么不同构建系统给出的执行顺序可以都正确。其二，拓扑排序与"按重要性排序"无关：它只尊重依赖方向，不比较任务优劣；要加上工期、优先级的排序属于调度问题的深水区，那是运筹学的地盘。

两套实现：摘果法与深度优先法

第一套实现就是存在性证明的直接翻译，即 Kahn 算法：反复摘"入度为零的果子"，摘掉后它的出边连带的顶点入度减一，新的零入度果子继续摘：

from collections import deque
import networkx as nx

def topo_kahn(G):
    """Kahn 算法：返回拓扑序；有环返回 None"""
    indeg = {v: G.in_degree(v) for v in G.nodes}
    queue = deque(v for v, d in indeg.items() if d == 0)   # 首批果子
    order = []
    while queue:
        u = queue.popleft()
        order.append(u)                    # 摘果入序
        for v in G[u]:
            indeg[v] -= 1                  # 松动下游
            if indeg[v] == 0:
                queue.append(v)
    return order if len(order) == len(G.nodes) else None   # 摘不完 = 有环

ops = nx.DiGraph([("侦察","定案"),("粮草","开拔"),("定案","开拔"),
                  ("征船","渡河"),("开拔","渡河"),("侦察","征船")])
print("行军次序表:", topo_kahn(ops))
print("nx 对照:", list(nx.topological_sort(ops)))
​

输出里"开拔"必然排在"定案"与"粮草"之后，"渡河"压轴——依赖全部得到尊重。而若图里出现环，队列终会枯竭、order 短于顶点总数，函数安静地返回空值：Kahn 天生自带环检测，这也是工程系统（包管理器、构建工具）几乎清一色选它的原因——排不出次序时，它能顺手指出"卡死"的那批任务。

第二套实现来自第 3 章深度优先的遗产：完成时刻的倒序即拓扑序。论证核心是把"回边"堵死——深度优先在无环图上不会产生回边（回边即环），于是所有边要么指向后代（完成更晚），要么横跨或指向前行（完成时刻必然更早），倒排后一切边都从先完成者指向后完成者：

def topo_dfs(G):
    """深度优先版：完成时刻倒序"""
    seen, finish = set(), []
    for s in G.nodes:
        if s in seen:
            continue
        stack = [(s, iter(G[s]))]
        seen.add(s)
        while stack:
            u, it = stack[-1]
            advanced = False
            for v in it:
                if v not in seen:
                    seen.add(v)
                    stack.append((v, iter(G[v])))
                    advanced = True
                    break
            if not advanced:
                finish.append(stack.pop()[0])      # 弹栈即完成
    return finish[::-1]

print("DFS 版:", topo_dfs(ops))
​

两套实现的对照值得细品：Kahn 像流水线（齐活一个上线一个，可并行、可增量），深度优先像探洞（一竿子插到底，回头收尾）。后者在造访"完成时刻"这件事上与第 4 章的强连通算法共用装备——Tarjan 的 SCC 算法正是在这套深度优先骨架上加了一个栈，两套问题共享了几乎全部的行军后勤。

演练：排课程与关键路径

把拓扑排序放到真实任务上。教务排课是最贴切的演练：课程是任务、先修关系是依赖，一张合法的培养方案就是课程图的拓扑序：

def curriculum(G):
    """排课：拓扑序 + 每门课的最早修读学期"""
    order = topo_kahn(G)
    if order is None:
        return "依赖有环，无法排课"
    earliest = {}
    for course in order:                     # 按拓扑序推进
        pres = list(G.predecessors(course))
        earliest[course] = 1 + max((earliest[p] for p in pres), default=0)
    return order, earliest

plan = nx.DiGraph([("高等数学","概率论"),("概率论","机器学习"),
                   ("编程入门","数据结构"),("数据结构","算法基础"),
                   ("算法基础","机器学习"),("编程入门","机器学习")])
order, term = curriculum(plan)
print("修读次序:", order)
print("最早学期:", term)
print("最快毕业学期:", max(term.values()))
​

这段代码顺手完成了关键路径的雏形：每门课的最早学期由最长先修链决定，那条最长的链就是"一分钟也省不下来"的关键路径——工程项目管理里工期估算的正统算法，正是把这套"最早开始时刻"的递推在任务图上跑一遍，再倒着跑一遍"最晚允许时刻"，两者的差给出机动时间，零机动的任务串成关键路径。

复杂度与带环救援

两套实现的账单都与"顶点数加边数"同阶——Kahn 的每顶点入队出队一次、每边松动一次；深度优先的每顶点每边各访问常数次。这是图算法里最干净的线性级别，也是它敢在千万级任务图上服役的底气。带环的依赖怎么办？第 4 章的强连通分量正是救援队：先缩点，把每个强连通分量压成一个"必须整体处理"的超级任务，骨架图（必然无环）跑拓扑排序，循环依赖的分量单独拎出来人工裁决——软件构建系统报告"循环依赖"时，给出需要人工拆解的模块清单，走的正是这条路。

应用与变体

拓扑排序的工业身影密集得惊人。构建系统按依赖图决定编译次序（第 10 章工程检阅再访）；数据管道调度器（工作流引擎）按任务依赖逐夜执行；包管理器解析安装次序；电子表格的公式重算按单元格依赖的拓扑序传播；区块链交易的确定性执行也靠它统一全网的排序共识。变体方面：字典序最小的拓扑序把队列换成最小堆（每步摘编号最小的可用任务），竞赛与实务都常见；所有拓扑序的枚举用回溯逐位试探，配合剪枝能处理中等规模的排程穷举；带并行轮次的排序（分层拓扑）把同层任务归为一波，问的是"最少几波能跑完"——恰是第 3 章广度优先的层次思想在依赖图上的转世。

⚠️ 常见坑：依赖方向画反。把"学机器学习前须先学概率论"画成"机器学习→概率论"，拓扑序会安静地把因果颠倒，一切照跑、全盘皆错——依赖图的边向定义要在动工前写进团队公约。

💡 关键直觉：拓扑排序把"缠绕的依赖"压成"笔直的队列"，靠的是无环这个前提。环是依赖世界的死结——识别它、拆解它、绕开它，是所有调度系统的第一课。

架桥与调度双双收官。下一章远征队深入补给线战场：网络流与匹配——在容量受限的通道里，怎么把物资送到最多。