入门：生成树、最小生成树与两种贪心
基于通用算法概念 · 核于 2026-07
速查
- 生成树（Spanning Tree）：连通无向图
G=(V,E)的一个子图，满足「连通（所有顶点都可达）+ 无环（是一棵树）+ 含全部 V 个顶点」——三者等价的推论是：恰好有 n−1 条边（n 是顶点数）。 - 最小生成树（MST）：在带权图的所有生成树里，边权之和最小的那棵——它是「用最低成本把所有节点连通」的数学模型，n 个顶点必选 n−1 条边。
- MST 的基础性质：①生成树有 n−1 条边、无环、连通；②一个连通图必有生成树；③给生成树加一条边必形成环（删环上任意一条边又恢复成生成树）。
- 切割性质（Cut Property，Kruskal 的依据）：把顶点集任意切成两半 S 和 V−S，横跨两半的边里权最小的那条，一定属于某棵 MST——只要每次都贪心选这种「跨切割的最小边」，就能逐步长出 MST。
- 环性质（Cycle Property）：任取图上一个环，环上权最大的那条边一定不属于 MST（除非所有边权相等）——这是反证「为什么删大边」的依据。
- Kruskal（按边贪心）：把所有边按权排序，从小到大逐条尝试加入，用并查集判环（两端点已在同一连通分量则跳过），直到选满 n−1 条——O(E log E)，主导项是排序。
- Prim（按点贪心）：从任一顶点出发，维护「已选集合 S」，每次从连接 S 与 V−S 的边里选权最小的，把对端顶点并入 S，用最小堆维护候选边——O(E log V)。
- 复杂度对比：Kruskal O(E log E)（排序主导，并查集近似 O(1)）；Prim 堆优化 O(E log V)、邻接矩阵朴素 O(V²)——取决于 E 与 V² 的关系。
- 稀疏选 Kruskal，稠密选 Prim：边少（E ≪ V²）时排序代价小，Kruskal 占优；边多（E ≈ V²）时 O(E log V) 退化，Prim 邻接矩阵 O(V²) 更稳。
- 唯一性：所有边权互不相同时 MST 唯一；存在相等权值时 MST 可能不唯一，但总权值必然相同——判唯一性看「同权边是否构成可选环」。
- 适用前提：连通、无向、带权；不连通图只能求最小生成森林；有向图对应的是最小树形图（朱-刘算法），不在本叶范围。
- 进阶顺序：Kruskal 与 Prim：两种贪心策略 → 选型与应用场景 → 参考。
一、生成树：连通无环的「骨架」
先把基础概念钉死。一个连通无向图 G = (V, E)（V 个顶点、E 条边）的生成树 T 是 G 的一个子图，满足三条互相等价的条件：
- 含全部顶点：T 的顶点集就是 V。
- 连通：任意两顶点在 T 中都有路径可达。
- 无环：T 里没有任何回路（是一棵树）。
由此推出一个最常考的事实：生成树恰好有 n−1 条边（n = |V|）。直觉理解：n 个孤立点要连成一棵树，第一条边连通 2 个点、每加一条边并入一个新点，共需 n−1 条；再多一条边就成环（不再无环），再少一条就断开（不再连通）。
原图（4 顶点 5 边） 生成树（4 顶点 3 边，无环连通）
A ─ 1 ─ B A ─ 1 ─ B
│ \ │ │ │
4 2 5 4 5
│ \ │ │ │
D ─ 3 ─ C D C
（挑出 1、4、5 三条边，连通无环）记一句话：「生成树 = 原图的骨架 = n 个顶点 + n−1 条边 + 连通无环」。
二、最小生成树：边权和最小的生成树
当图带权（每条边有个非负/任意实数权重）时，「最小生成树」就是在所有可能的生成树里挑出边权之和最小的那棵。它是工程问题「用最低成本把一群节点连通」的抽象：
- 城市之间架通信光缆，每条线路造价不同，求「连通所有城市且总造价最低」。
- 电路板布线、给村庄通水通电、聚类分析里把近邻点连成簇……
带权图 MST（边权和 = 1+2+3 = 6）
A ──1── B A ──1── B
│\ │ │ │
4 2 5 │ 2 │
│ \ │ │ │
D ──3── C D ──3── C ← 舍弃 4、5 两条
总权 1+2+3+4+5=15 （1、2、3 三条边连通无环，和最小）注意几个常被混淆的点：
- MST 必然有 n−1 条边（它是生成树）——不是「选最少条数的边」，而是「选权和最小的 n−1 条连通边」。
- 不连通图没有生成树：求 MST 前先判连通性；若不连通，算法（Kruskal）会返回一个最小生成森林——每个连通分量一棵树。
- 负权边：MST 的定义允许任意实数权（包括负），算法照常工作；但别和「最短路」混——最短路的负权要担心负环，MST 没有这个问题。
三、贪心为什么对：切割性质与环性质
Kruskal 和 Prim 都是贪心算法——每步都选「当前看起来最优」的边，不回溯。贪心能保证全局最优，靠的是两条性质：
切割性质（Cut Property）—— Kruskal / Prim 的共同基石
把顶点集任意切成两半 S 和 V−S（这叫一个「切割」），那么横跨这个切割的所有边里，权最小的那条，一定属于某棵 MST。
证明很直观：假设某棵 MST T* 不含这条最小跨边 e，把 e 加进 T* 必然在某个跨切割的位置形成环，环上一定有另一条跨切割的边 e'（否则不构成跨切割的环），而 w(e) ≤ w(e')，删掉 e' 得到一棵总权不增的新生成树 T'——所以 e 能进某棵 MST。
这条性质是 Prim 的直接依据（Prim 每步切的 S 就是「已选集合」），也是 Kruskal 选「两端不在同一分量」的边的依据（分量并合相当于切了一刀）。
环性质（Cycle Property）—— 删大边
图上任取一个环，环上权最大的那条边一定不属于某棵 MST（除非所有边权相等）——因为总能用环上别的边替代它而不增总权。这是反向「为什么不会选进最大边」的依据。
一句话总结：贪心选小边对、贪心弃大边也对，根源都是这两条性质。
四、两种贪心思路对比
| 维度 | Kruskal（按边贪心） | Prim（按点贪心） |
|---|---|---|
| 贪心对象 | 边（全局排序逐条挑） | 顶点（从一点向外长） |
| 核心动作 | 排序边 → 逐条试加 → 并查集判环 | 维护已选集 → 选跨集合最小边 |
| 数据结构 | 边集数组 + 并查集 | 邻接表 + 最小堆 |
| 复杂度 | O(E log E)（排序主导） | O(E log V)（堆） / O(V²)（矩阵朴素） |
| 边权相同时 | 选边顺序影响细节，但总权一致 | 同理 |
| 强项 | 稀疏图（E 小，排序快） | 稠密图（E≈V²，矩阵朴素更稳） |
| 适合表示 | 边集数组（天然按边遍历） | 邻接矩阵 / 邻接表 |
Kruskal 直觉：把所有边铺在桌上按价格排好，从最便宜的开始拿，只要这条边不和你已拿的边形成环就留下，凑够 n−1 条停——「全局挑最便宜」。
Prim 直觉：从一个种子顶点开始，每次向外伸出一只手抓一条连着已选部分的最便宜的边，把对端顶点拉进已选集合，重复到所有顶点都进来——「从一个点长成一棵树」。
两者都正确，都基于切割性质，只是「切法」和「维护最小边的数据结构」不同。
五、稀疏与稠密：怎么选
这是 MST 选型的核心决策，依据是 E 与 V² 的相对大小：
- 稀疏图（E ≪ V²，比如 E = O(V)）：选 Kruskal。排序 O(E log E) 很小，并查集判环近似 O(1)，总 O(E log E) 远小于 Prim 的 O(E log V)——而且 Kruskal 天然用边集数组，输入就是边列表，省去建图的步骤。
- 稠密图（E ≈ V²，比如完全图）：选 Prim 邻接矩阵朴素版 O(V²)。此时 E 很大，O(E log V) ≈ O(V² log V) 反而比朴素 O(V²) 慢——朴素的「每次扫一遍找最小」在稠密时反而最优，且常数极小。
- 通用/不确定：直接用 Prim 堆优化 O(E log V) 或 Kruskal O(E log E) 都行，两者量级相近；竞赛里 Kruskal 更常被无脑套用（代码短、并查集好写）。
记住口诀：「边少选 Kruskal（排序省）、边多选 Prim（矩阵 O(V²) 稳）」。
下一步
理解了 MST 的定义与两种贪心思路后，下一步是把 Kruskal 与 Prim 的代码与复杂度掰开揉碎——排序 + 并查集判环、堆 + 松弛，见Kruskal 与 Prim：两种贪心策略。