CSP-J 初赛（以满分为目标）：第二十八课《生成树与最小生成树——城市之间到底应该修哪些路？》

第二十八课：生成树与最小生成树

——城市之间到底应该修哪些路？

上一课我们学习了BFS 广度优先搜索。

我们已经学会了：

怎样把一张图“走一遍”。

但是今天我们换一个问题。

假设有5个城市：

A B C D E

城市之间原本有很多条可以修建的道路：

5 A -------- B |\ /| 2| \4 1/ |3 | \ / | C -------- D 2 \ E

如果政府希望：

所有城市都能互相到达，但是修建的道路总费用尽可能低。

应该怎么选择道路？

这就是今天要学习的：

生成树（Spanning Tree）

以及：

最小生成树（Minimum Spanning Tree，MST）

而这也是图论部分非常重要的内容。它的核心原则是：在连通网中选择若干条边，使所有顶点连通，并且选择n−1 条边；对于最小生成树，还要求这些边的权值之和最小。

一、先从“树”开始回忆

我们之前学过树。

例如：

A / \ B C / \ D E

这是一棵树。

树有几个非常重要的特点：

特点1：所有结点连通

从A可以到B、C、D、E。

特点2：没有环

不存在：

A → B → C → A

这样的回路。

特点3：n个结点的树有n−1条边

例如：

3个点 → 2条边 4个点 → 3条边 5个点 → 4条边

所以：

n个顶点的树恰好有n-1条边

这个结论在今天非常重要。

二、图和树是什么关系？

我们可以把：

树看成一种特殊的图。

例如：

图： A —— B | \ | | \ | C —— D

这里有一个环：

A → B → D → C → A

所以它不是树。

但是我们删掉一条边：

A —— B | | | | C —— D

就可能变成一棵树。

因此：

从一个图中“挑出一些边”，也可以得到一棵树。

这就是：

生成树

三、什么叫“生成树”？

这个名字其实非常形象。

“生成”可以理解为：

从原来的图中选出一些边，把所有顶点连接起来，生成一棵树。

注意三个关键词：

生成树 ↓ 来自原图 ↓ 包含所有顶点 ↓ 连通 ↓ 没有环

所以：

生成树 = 包含原图所有顶点的树

四、为什么叫“生成”树？

假设原来的图是：

A / | \ B--C--D \ | / E

我们从里面挑几条边：

A | B / \ C E | D

现在：

• A有了

• B有了

• C有了

• D有了

• E有了

所有顶点都还在。

但是边减少了，而且没有环。

于是：

这就是原图的一棵生成树。

五、一个图可能有很多棵生成树

这是非常重要的。

例如：

A / \ B---C

原图有三条边：

A-B A-C B-C

我们只需要两条边就可以把三个点连起来。

可以选择：

A-B A-C

得到：

A / \ B C

也可以选择：

A-B B-C

得到：

A | B \ C

还可以选择：

A-C B-C

所以：

一个图通常可以有很多棵生成树。

题目问：

“图的生成树（ ），n个顶点的生成树有（ ）条边”，答案对应的是不唯一和n−1。

六、生成树一定有多少条边？

假设原图有：

n

个顶点。

如果生成树也包含这n个顶点，那么因为：

n个顶点的树恰好有n−1条边

所以：

E = n−1

例如：

这个结论是CSP-J初赛非常值得记忆的公式。

七、为什么不能少于n−1条边？

假设有：

A B C D

4个城市。

如果只有2条道路：

A —— B C —— D

显然：

A、B

是一块。

C、D

是另一块。

它们没有连接。

所以4个城市想全部连起来：

至少需要3条边

也就是：

n−1

八、为什么又不能超过n−1条边？

因为超过以后就一定有可能产生环。

例如4个点：

A —— B | | D —— C

这里：

A → B → C → D → A

形成了一个环。

所以它不是树。

因此树必须满足：

n个顶点 + n−1条边

并且：

连通且无环

九、现在加入“道路费用”

前面只考虑：

能不能把城市连起来？

现在考虑：

花多少钱？

例如：

A -------- B \ / \ / \ / C

道路费用：

A-B：10 A-C：2 B-C：3

如果选择：

A-C B-C

总费用：

2 + 3 = 5

如果选择：

A-B A-C

总费用：

10 + 2 = 12

显然：

5 < 12

所以第一种更好。

十、这就是“最小生成树”

如果图是一张：

带权连通图

也叫：

连通网

那么：

在所有生成树中，权值总和最小的那一棵，就是最小生成树。

英文：

Minimum Spanning Tree

缩写：

MST

定义是：

连通网中所有生成树中权值之和为最小的生成树。

十一、千万不要把“最小生成树”理解错

最小生成树：

❌ 不是边数最少

因为所有生成树本来就都是：

n−1

条边。

所以边数都一样。

真正比较的是：

权值总和

例如：

生成树A： 边权 1 + 4 + 6 = 11 生成树B： 边权 2 + 3 + 4 = 9 生成树C： 边权 1 + 2 + 5 = 8

那么：

MST是生成树C

十二、生活中的最小生成树

这个问题特别适合讲给初学者。

假设有5个城市：

北京 上海 广州 深圳 成都

现在要铺设光纤。

两座城市之间可以铺光纤，但不同路线价格不同。

目标：

让所有城市都能通过光纤互相通信，同时总建设费用最低。

我们不需要：

所有城市两两之间都直接连接

只需要：

所有城市连成一个整体

因此：

城市网络 ↓ 选择部分道路 ↓ 所有城市连通 ↓ 不能有环 ↓ n个城市选n-1条边 ↓ 总费用最小 ↓ MST

这就是最小生成树最经典的应用。

我们一般用“n个城市建网，如何选择n−1条线路，使总费用最少？”来说明最小生成树的应用。

十三、MST最重要的直觉：便宜的路优先

假设有：

A —— B 10 A —— C 2 B —— C 3

我们自然会想：

先修2元的。

然后：

再修3元的。

这样：

A —— C —— B

所有城市已经连通。

总费用：

2 + 3 = 5

没有必要再修10元的道路。

所以最小生成树有一个非常重要的基本思想：

尽可能选择权值小的边，但不能形成回路。

十四、但是这里有一个“陷阱”

初学者很容易说：

“那我把所有最小的边都选了不就行了吗？”

不行！

因为：

不能形成回路。

看：

A —— B \ / \ / C

如果三条边都是1：

A-B = 1 A-C = 1 B-C = 1

如果全部选：

A —— B \ / \ / C

出现环。

而生成树必须：

连通 + 无环

所以第三条边必须舍弃。

最终：

A —— B \ \ C

两条边就够了。

十五、最小生成树的核心口诀

请大家记住：

小边优先，但不能成环。

再加一句：

最后选够n−1条边。

所以：

MST ↓ 小边优先 ↓ 不能成环 ↓ 选n-1条 ↓ 所有点连通

十六、今天先认识两种经典算法

解决最小生成树有很多方法。

我们重点介绍了两种：

① Kruskal 克鲁斯卡尔算法

特点：

按边来考虑。

可以理解为：

加边法

② Prim 普里姆算法

特点：

按顶点来考虑。

可以理解为：

加点法

我们将 Kruskal 描述为“加边法”，将 Prim 描述为“加点法”。

不过今天，我们先把：

生成树和最小生成树的概念

真正理解清楚。

下一课再专门学习：

Kruskal到底怎样一步一步选边？

十七、先认识Kruskal：像“选道路”

Kruskal的思路特别适合小学生理解。

假设有：

A-B：4 A-C：1 B-C：2 B-D：5 C-D：3

第一步：

按道路价格从小到大排序。

得到：

1：A-C 2：B-C 3：C-D 4：A-B 5：B-D

然后从前往后看。

选择1：A-C

可以！

A —— C

选择2：B-C

可以！

A —— C —— B

选择3：C-D

可以！

A —— C —— B | D

现在4个顶点已经全部连通。

我们已经选了：

4−1=3

条边。

结束！

总费用：

1+2+3=6

这就是一棵最小生成树。

十八、为什么不选择A-B？

因为到那个时候：

A | C | B

已经连通。

如果再加：

A —— B

就形成：

A —— B \ / \ / C

出现环。

所以：

便宜的边优先，但会成环就跳过。

这就是Kruskal最核心的思想。

按照权值从小到大的顺序选择边，并保证所选边不构成回路。

十九、Prim又是什么？

Prim换一个思路。

Kruskal想的是：

“哪条道路便宜？”

Prim想的是：

“我现在已经建设好的区域，下一步连接哪个新城市最便宜？”

例如：

B / \ A---C \ D

假设从A开始。

一开始：

已经加入： A

然后看：

A能连接谁？

选择最便宜的一条：

A → B

于是：

已经加入： A B

然后继续寻找：

A、B周围有哪些还没加入的城市？

选择最便宜的边。

不断扩张：

一个点 ↓ 两个点 ↓ 三个点 ↓ …… ↓ 所有点

讲义对Prim的定义就是从一个顶点开始，不断寻找与当前顶点集合相邻且代价最小的边，将新的顶点加入集合，直到所有顶点都加入。

二十、Kruskal和Prim的直观区别

可以想象两种修路队。

Kruskal修路队

拿着一张：

全国所有道路价格表

然后：

最便宜 ↓ 第二便宜 ↓ 第三便宜 ↓ ……

不断选。

所以：

Kruskal：看边

Prim修路队

从一个城市出发：

城市A ↓ 扩张到B ↓ 扩张到C ↓ 扩张到D ↓ ……

所以：

Prim：看点

二十一、一个非常重要的考试对比

经典复杂度与适用场景：

• Kruskal主要对边操作，复杂度写作 O(e log⁡e)，比较适合稀疏图；

• Prim主要对顶点操作，讲义给出的版本复杂度为 O(n2)，比较适合稠密图。

这里先理解“加边 vs 加点”即可，复杂度和代码实现放到后面专门讲。

二十二、生成树、最小生成树、最短路径不要混淆

这是初学者特别容易混淆的三个概念。

① 生成树

要求：

所有顶点连通、没有环。

不一定考虑费用。

② 最小生成树

要求：

所有顶点连通、没有环，并且所有边权之和最小。

③ 最短路径

要求：

从一个顶点到另一个顶点，寻找一条路径总权值最小的路线。

它们解决的问题不同。

二十三、举一个非常重要的区别

假设：

A —— B —— C \ / \-------/

道路：

A-B = 1 B-C = 1 A-C = 10

从A到C的最短路径：

A → B → C

费用：

1+1 = 2

这是：

最短路径

而最小生成树也是：

A —— B —— C

费用：

1+1=2

这里刚好一样。

但是：

它们不是同一个问题。

以后我们会专门学习：

最小生成树

和：

最短路径

不能混为一谈。

二十四、CSP-J初赛高频考点1

题目：

n个顶点的生成树有多少条边？

答案：

n−1

二十五、CSP-J初赛高频考点2

题目：

最小生成树指什么？

正确答案：

所有生成树中权值之和最小的生成树

二十六、CSP-J初赛高频考点3

题目：

一个图有n个顶点，它的生成树一定有n−1条边吗？

如果说的是：

生成树

答案：

一定

因为生成树本身就是一棵树。

二十七、CSP-J初赛高频考点4

题目：

一个图有多个生成树吗？

答案：

可能有很多棵。

例如三角形：

A / \ B---C

任意去掉其中一条边，都可以得到一棵生成树。

所以：

生成树通常不唯一

但要注意：

最小生成树也不一定唯一。

如果存在多条相同权值的道路，就可能存在多棵权值相同的最小生成树。

一个连通网可以存在多棵权值总和不同的生成树。

二十八、CSP-J初赛高频考点5

判断：

最小生成树就是边数最少的生成树。

❌ 错。

因为：

所有生成树都有n−1条边。

真正比较的是：

权值总和。

二十九、CSP-J初赛高频考点6

判断：

Kruskal算法按照边权从小到大选择边。

✅ 对。

但是后半句更重要：

不能让所选边形成回路。

所以完整口诀：

Kruskal：边权排序，小边优先，不能成环

三十、CSP-J初赛高频考点7

判断：

Prim算法每次选择图中全局最小的边。

❌ 不准确。

Prim选择的是：

与当前已经加入的顶点集合相邻的最小代价边。

这是Prim和Kruskal很重要的区别。

三十一、把今天内容浓缩成一张图

图 │ ┌─────────┴─────────┐ │ │ 普通图 带权连通图 │ ↓ 生成树 │ n个顶点 │ n-1条边 │ ┌─────────┴─────────┐ │ │ 连通 无环 │ │ └─────────┬─────────┘ ↓ 生成树们 │ 比较权值总和 │ ↓ 最小生成树 MST │ ┌───────────┴───────────┐ │ │ Kruskal Prim 加边法 加点法 │ │ 小边优先 从一个点 不能成环 不断扩张

三十二、今天最重要的“4个必须记住”

如果这一课结束以后，孩子只能记住4件事，我希望是：

① 生成树

包含原图所有顶点的树。

② n个顶点的生成树

n−1条边

③ 最小生成树

所有生成树中，权值总和最小的那一棵。

④ MST的基本思想

尽可能选择小权值的边，但不能形成环，最终选择n−1条边。

这些是最小生成树的核心知识。

三十三、课堂练习

练习1

一棵树有20个顶点。

问：

有多少条边？

答案：

20−1=19

练习2

一个连通图有8个顶点。

它的任意一棵生成树有多少条边？

8−1=7

练习3

下面哪个是最小生成树的正确描述？

A. 边数最少的树
B. 顶点数最少的树
C. 权值总和最小的生成树
D. 权值最大的生成树

答案：

C

练习4

Kruskal算法的基本思想是什么？

回答：

按照边权从小到大选择边，但是不能形成环。

完全正确。

三十四、给大家留一道思考题

看下面的图：

1 A ------- B |\ /| 4| \ / |5 | \ / | | \ / | C ------- D 2

假设：

A-B = 1 C-D = 2 A-C = 4 B-D = 5 A-D = 3 B-C = 6

问题：

如果使用Kruskal算法，应该按照什么顺序考虑这些边？

答案先不要急着算。

第一步只需要：

把所有边按照权值从小到大排序。

也就是：

1 2 3 4 5 6

然后：

一条一条检查，能加就加，成环就跳过。

下一课我们就用这张图，手工模拟完整的Kruskal算法，并正式认识一个非常重要的数据结构：

并查集（Union-Find / DSU）

到那时孩子会发现一个特别漂亮的关系：

Kruskal ↓ 判断两个点是否已经连通 ↓ 并查集 ↓ 快速判断“加这条边会不会成环”

这样就会把今天的“小边优先、不能成环”，真正变成可以写进C++程序的算法。