# 生成树与最小生成树算法

> IB 数学 AI HL · IB AI HL
> 来源: https://www.owlsprep.com/zh/study/ib-math-ai-hl-u5-spanning-trees-and-minimum-spanning/

本模块介绍生成树，以及IB AI HL中用于寻找最小生成树（MST）的两种标准算法。你将学习如何应用克鲁斯卡尔算法和普里姆算法解决网络优化问题。

**先修:** [基础图术语和带权图](https://www.owlsprep.com/zh/study/ib-math-ai-hl-u5-graph-terminology-weighted-graphs/)

## 学习目标

- 识别连通无向图的生成树
- 应用克鲁斯卡尔算法寻找最小生成树
- 应用普里姆算法寻找最小生成树
- 计算优化问题中最小生成树的总权重

## 什么是生成树？

**生成树** — 连通无向图的一个连通无环子图，包含原图的所有顶点。对于有$n$个顶点的图，任何生成树都恰好包含$n-1$条边。

*例:* 4顶点图的生成树总是恰好有3条边。

大多数连通图存在多个可能的生成树。生成树通过删除环简化原图，同时保留所有顶点之间的连通性，因此在网络设计问题中非常有用。

**例题:** 为顶点为$A, B, C, D$、边为$AB, BC, CD, DA, AC$的连通图画出一棵合法的生成树。

1. 统计顶点数量：$n = 4$，因此生成树需要$n-1 = 3$条边。
2. 选择3条边连接所有顶点且无环。一个合法选择是边$AB, BC, CD$。
3. 验证：所有4个顶点都被包含，子图连通且无环，因此这是一棵合法的生成树。

## 最小生成树（MST）

**最小生成树（MST）** — 对于带权连通无向图，最小生成树是边权重之和小于等于该图其他任何生成树总权重的生成树。

*记法:* Total weight: $W = \sum_{e \in T} w(e)$ where $T$ is the spanning tree

*例:* 连接3个城市、边权重为2、3、5的最小生成树总权重为5，即两条最小连接边的和。

最小生成树可用于解决实际问题，例如找到连接多个城镇的最低成本管道网络，或设计最低成本的光纤网络。任何带权连通图都至少存在一棵最小生成树；如果所有边权重都不同，则恰好存在一棵最小生成树。

**例题:** 一个图有3个顶点$A, B, C$，边权重为$w(AB) = 4$，$w(AC) = 2$，$w(BC) = 3$。求最小生成树的总权重。

1. 对于$n=3$个顶点，最小生成树需要$3-1=2$条边。
2. 选择连接所有顶点且无环的两条最小边：$AC$（权重2）和$BC$（权重3）。
3. 权重求和：$2 + 3 = 5$。这就是最小生成树的总权重。

## 克鲁斯卡尔算法

克鲁斯卡尔算法是一种贪心算法，它按权重从小到大依次添加边来构建最小生成树，跳过任何会形成环的边。

1. 将所有边按权重从小到大排序
2. 从空的最小生成树边集开始
3. 如果下一条最小边不会与现有边形成环，则添加它
4. 重复直到获得$n-1$条边（所有顶点连通）

> **tip**
>
> 当图以边列表形式给出而非邻接矩阵时，克鲁斯卡尔算法最容易使用。

**例题:** 使用克鲁斯卡尔算法求4顶点图（边为$AB(1), AC(4), BC(2), BD(5), CD(3)$）的最小生成树总权重。

1. 按权重排序边：$AB(1), BC(2), CD(3), AC(4), BD(5)$。
2. 添加$AB$：无环，当前边：$\{AB\}$，连通顶点：$\{A,B\}$。
3. 添加$BC$：无环，当前边：$\{AB, BC\}$，连通顶点：$\{A,B,C\}$。
4. 添加$CD$：无环，连接D，当前边：$\{AB, BC, CD\}$（4顶点共3条边，完成）。
5. 总权重：$1 + 2 + 3 = 6$。

## 普里姆算法

普里姆算法同样是贪心算法，但它从单个顶点开始构建最小生成树，重复添加连接新顶点到现有树的最小边。

1. 选择任意起始顶点并将其添加到最小生成树集合
2. 找到连接最小生成树集合内顶点和集合外顶点的最小权重边
3. 将这条边和新顶点添加到最小生成树集合
4. 重复直到所有顶点都被添加到最小生成树集合

> **tip**
>
> 当图以邻接矩阵形式给出时，普里姆算法最容易使用，且不需要显式检查环。

**例题:** 从顶点$A$开始使用普里姆算法，求同一个4顶点图（边为$AB(1), AC(4), BC(2), BD(5), CD(3)$）的最小生成树总权重。

1. 初始最小生成树集合：$\{A\}$，未添加任何边。
2. 从$A$到集合外的最小边是$AB(1)$。添加$AB$和$B$，最小生成树集合：$\{A,B\}$。
3. 从$\{A,B\}$到集合外的最小边是$BC(2)$。添加$BC$和$C$，最小生成树集合：$\{A,B,C\}$。
4. 从$\{A,B,C\}$到集合外的最小边是$CD(3)$。添加$CD$和$D$，所有顶点都已包含。
5. 总权重：$1 + 2 + 3 = 6$，与克鲁斯卡尔算法结果相同。

**方法对比**

两种算法都能得到正确的最小生成树，但它们适合不同的输入格式：

- **克鲁斯卡尔算法** — 先对边排序，添加边时避免形成环
  - 优点: 适合边列表、稀疏图
  - 缺点: 每一步都需要检查是否有环

- **普里姆算法** — 从起始顶点开始构建，每次添加最近顶点
  - 优点: 不需要显式检查环，适合邻接矩阵
  - 缺点: 对于初学者，任意起点的方式不够直观

## 常见错误

- **错误做法:** 停止时边数量错误
  - 原因: 忘记$n$顶点生成树一定恰好有$n-1$条边
  - 正确做法: 解题开始时先计算$n-1$，得到该数量边后停止
- **错误做法:** 在克鲁斯卡尔算法中添加会形成环的边
  - 原因: 添加下一条最小边时忘记检查环
  - 正确做法: 始终确认新边连接的顶点不在已有的连通分量中
- **错误做法:** 认为普里姆算法中起始顶点会改变最小生成树总权重
  - 原因: 假设不同起点会得到不同总权重
  - 正确做法: 即使边集合不同，任何起点得到的最小生成树总权重都相同
- **错误做法:** 混淆最小生成树和最大生成树
  - 原因: 错误地选择最大边而非最小边
  - 正确做法: 再次确认题目要求最小权重，始终从权重最小的边开始选择
- **错误做法:** 所有顶点连通后继续添加额外边
  - 原因: 没有提前停止，继续添加边
  - 正确做法: 所有顶点连通后立即停止，额外边只会增加总权重并形成环

## 速查表

| 概念/算法 | 关键步骤 | 关键性质 |
| --- | --- | --- |
| 生成树 | 包含所有顶点，连通，无环 | $n$顶点$\rightarrow$ $n-1$条边 |
| 最小生成树 | 总边权重最小的生成树 | 所有连通带权图都至少存在一棵最小生成树 |
| 克鲁斯卡尔算法 | 按权重排序边，添加最小边，避免环，得到$n-1$条边后停止 | 最适合边列表/稀疏图 |
| 普里姆算法 | 从任意顶点开始，添加连接新顶点的最小边，重复直到所有顶点都被包含 | 最适合邻接矩阵/稠密图，不需要检查环 |

## 下一步

生成树和最小生成树算法是IB AI HL图论优化的核心概念。它们是更高级网络问题（如最短路径寻找和最大流）的基础，这些问题也常出现在考试中。最小生成树问题常出现在试卷1和试卷2中，通常结合运输网络设计或通信基础设施等实际背景。练习两种算法直到你能熟练应用，将帮助你在这些常见考题中获得满分。

- [图论应用：中国邮路问题（CPP）和旅行商问题（TSP）](https://www.owlsprep.com/zh/study/ib-math-ai-hl-u5-graph-theory-applications-cpp-and/)

---

来自 [OwlsPrep](https://www.owlsprep.com) —— A-Level / IB / AP / IGCSE 免费学习指南，依据官方考纲编写。原页面：https://www.owlsprep.com/zh/study/ib-math-ai-hl-u5-spanning-trees-and-minimum-spanning/