算法与数据结构

最小生成树与拓扑排序

04-图与网络核心预计 20 分钟最小生成树拓扑排序KruskalKahn
学习状态：

一句话定义

最小生成树（Minimum Spanning Tree, MST）在无向连通带权图中选出 V−1 条边使全图连通且总权最小，Kruskal 按边贪心 + 并查集判环（O(E log E)）、Prim 按点贪心 + 堆（O(E log V)）；拓扑排序（Topological Sort）把有向无环图（DAG）排成「每条边都从前指向后」的线性序，Kahn 算法用入度表 + 队列在 O(V+E) 完成。

为什么重要

MST 回答「用最小代价把所有点连起来」——电网、管网、聚类分割、近似算法基座；拓扑排序回答「谁先谁后」——构建系统（make/npm）、任务调度、课程规划、数据管道。两者还是 kp-025 贪心正确性证明（切割定理）与 kp-030 并查集的第一个杀手级应用场景。

前置知识

kp-016（图与遍历）；Kruskal 需要 kp-030 并查集（可先读其原理部分）。

核心概念

  • 生成树：含全部 V 个顶点的无环连通子图，恰 V−1 条边。
  • 切割定理（Cut Property）：任意把点集切成两半，横跨切口的权最小边必属于某棵 MST——贪心正确性的核心。
  • Kruskal：边按权排序，逐一尝试加入，用并查集跳过成环边；复杂度 O(E log E)。
  • Prim：从任一点出发，每次取「树外点连接树的最小边」（小顶堆维护）；复杂度 O(E log V)，稠密图配朴素版 O(V²)。
  • DAG 与拓扑序：DAG 至少存在一个拓扑序；有环则不存在。
  • Kahn 算法：入度为 0 的点入队，出队后删其出边使后继入度减一，减到 0 入队；结束时输出数 < V ⇔ 有环。
  • DFS 逆后序：DFS 完成时间逆序也是一个拓扑序。

直观类比

Kruskal 像「全国修高速公路按造价从低到高批项目，修成环的项目一律毙掉」；Prim 像「从北京出发，每一步把离现有路网最近的城市接入」。拓扑排序则是「毕业倒排期」：没有先修课的课（入度 0）先排，修完解锁下一批。

原理与机制

切割定理证明骨架：设 T 为一棵 MST，e 为切口的最小横跨边；若 e ∉ T，把 T 中另一条横跨边 f 换成 e，环性质保证仍连通且总权不增——故存在包含 e 的 MST。Kruskal 的「并查集判环」正是维护「已选边构成的连通关系」：两端已同根则该边成环。Kahn 的正确性：入度 0 ⇔ 无前驱，输出它不破坏约束；归纳可得整个序列合法；有环图的环上点入度永不为 0，故输出计数不足即报环。

Kahn 伪代码:
    统计全部入度 ; 队列 ← 入度为0的点
    当 队列非空:
        u ← 出队 ; 输出 u ; cnt++
        对于 v ∈ adj[u]:
            若 --indeg[v] == 0: v 入队
    若 cnt < |V|: 存在环

图示

MST（Kruskal 过程）:        A ─1─ B
边排序: AB(1) BC(2) AC(3) AD(4)     |    \
AB ✓ → BC ✓ → AC ✗(成环) → AD ✓     3      4
结果边集 {AB, BC, AD}，总权 7    C ─2─ D ─
拓扑序示例:  A→B, A→C, B→D, C→D
             ⇒ 序列 A, B, C, D（或 A, C, B, D，不唯一）

实例或案例

  • 电网/光缆铺设最小造价：经典 MST；图像分割（最小割与 MST 的联系）。
  • 构建系统：npm/make 的依赖解析即拓扑排序 + 环检测（循环依赖报错）。
  • 任务调度平台（Airflow 类 DAG）：拓扑序决定执行批次；同层可并行。
  • 最短路径 DAG 特例：先拓扑排序再按序松弛，O(V+E) 一步到位。

常见误区

  • 认为 MST 唯一：边权有重复时 MST 可能多棵（但总权唯一）。
  • 在有环图上跑拓扑排序还期待完整输出：输出数 < V 正是环的判据，必须检查。
  • Kruskal 忘记判环直接加边：得到的是「排序后的普通子图」，不一定是树。
  • 把「全局最小边一定在 MST 中」误读成「每一步取的最小边都在」：切割定理保证的是「存在某棵 MST 含全局最小边」，Kruskal/Prim 的逐步正确性各自由不变量独立保证。

自测题

  1. 对图 A─1─B、B─2─C、A─3─C、C─4─D、B─5─D 求 MST（Kruskal 列出每步取舍）。

答案要点：AB(1)✓、BC(2)✓、AC(3)✗成环、CD(4)✓、BD(5)✗；边集 {AB,BC,CD} 总权 7。

  1. 如何在 O(V+E) 内判断有向图是否为 DAG？

答案要点：Kahn 拓扑排序，输出计数等于 V 则是 DAG，否则有环。

  1. 证明「DFS 完成时间的逆序是拓扑序」。

答案要点：对任意边 u→v，DFS 中 v 必在 u 之前完成（v 或为 u 后代、或已先完成），故逆后序中 u 在 v 前。

与其他知识点的关系

kp-030 并查集支撑 Kruskal 判环；kp-025 贪心与切割定理互为示例与工具；kp-019 的 SCC 缩点后也要再拓扑排序；kp-028 的区间 DP 与「DAG 上做 DP」思想同源。

延伸阅读

《算法导论》第 21 章「最小生成树」与第 20.4 节「拓扑排序」；Kruskal 1956、Prim 1957 原始论文。

前置知识点

相关知识点