第6章 架桥铺路：最小生成树与行军调度

第 6 章 · 架桥铺路：最小生成树与行军调度

章节摘要：最短路战役解决"点到点怎么走"，本章的战役换了一道题：把远征队控制的所有据点连成一张通行网，总造价还要最低。这就是最小生成树问题——Prim 从大本营向外生长，Kruskal 把所有候选桥梁按造价排序逐条审批，两条路线殊途同归，背后共用一条"安全边定理"。本章第三节引入拓扑排序：当任务之间有先后依赖、构成有向无环图时，如何排出一张不违反任何依赖的行军次序表。生成树管"连得省"，拓扑序管"排得对"，两件兵器合起来撑起工程世界大半的连接与调度问题。

本章知识点清单

读完本章，下列考核点应当逐条过关：

1. 给出生成树与森林的定义，证明" n 个顶点的连通图其生成树恰含 n 减一条边"。
2. 陈述并证明切割安全定理，解释它与 Prim、Kruskal 各自的关系。
3. 手写 Prim 的朴素版与堆优化版，说清它与 Dijkstra 在"键值"上的微妙差异。
4. 手写 Kruskal，并解释并查集在其中担任成环检测器的原因。
5. 用反证证明拓扑序存在当且仅当有向图无环，手写 Kahn 算法与深度优先两种实现。
6. 用拓扑序解决依赖调度问题，并对接第 4 章"缩点成无环骨架"的预处理思路。

核心概念速览

金句：生成树算法的合法性不靠运气，靠定理——每一步选的边都落在"切割的轻边"上，贪心便有了免死金牌。

子章节导航

第 1 节"Prim 算法：从大本营生长的补给网"以修补给网的场景切入，演示"已建区域整体向外找最便宜接口"的生长逻辑，给出朴素与堆优化两种实现，并与 Dijkstra 做一次逐行对照——两者代码形似，键值定义一字之差，结论天差地别。

第 2 节"Kruskal 算法：按造价排序的架桥清单"走另一条路：不管据点在哪，把全部边按造价升序排好，逐条审批、成环则弃。第 4 章的并查集在这里担任要职，稀疏图上它是不可撼动的首选。

第 3 节"拓扑排序：行军次序的调度表"从依赖调度场景出发，给出 Kahn 入度法与深度优先法两套实现，讲清"有环无解"的判定，并把第 4 章强连通缩点接进来——带环依赖的工程标准解法就是先缩点再排序。

子章节之间的逻辑关系

一句话论点：前两节是一枚硬币的两面——同一个定理、两种切法；第三节换防——从"连"的问题切到"序"的问题，靠第 4 章的无环判定收口。

   切割安全定理
   ┌────┴────┐
   ▼         ▼
 Prim      Kruskal
 逐点生长   逐边审批
 稠密友好   稀疏首选（并查集）
   └────┬────┘
        ▼
   连通且无环 = 树
        ┆
   "无环"这一性质 → 第3节 拓扑排序的入场券
   DAG + 依赖关系 = 调度表
​

前置知识与后续延伸

前置：第 2 章的两种存储结构、第 4 章的并查集（Kruskal 直接调用）与回边判环（拓扑排序的存在性判定）、第 5 章 Dijkstra 的堆优化实现（Prim 的代码近亲）。

后续延伸：最小生成树是网络设计（电网、光缆、管道）的数学原形，也是聚类分析（第 10 章社区发现的单链法）与近似算法（旅行商问题的两倍近似）的跳板；拓扑排序是构建系统、包管理器、任务编排引擎的核心例程，第 10 章工程检阅将回到它的生产线。