第二十八课生成树与最小生成树——城市之间到底应该修哪些路上一课我们学习了BFS 广度优先搜索。我们已经学会了怎样把一张图“走一遍”。但是今天我们换一个问题。假设有5个城市A B C D E城市之间原本有很多条可以修建的道路5 A -------- B |\ /| 2| \4 1/ |3 | \ / | C -------- D 2 \ E如果政府希望所有城市都能互相到达但是修建的道路总费用尽可能低。应该怎么选择道路这就是今天要学习的生成树Spanning Tree以及最小生成树Minimum Spanning TreeMST而这也是图论部分非常重要的内容。它的核心原则是在连通网中选择若干条边使所有顶点连通并且选择n−1 条边对于最小生成树还要求这些边的权值之和最小。一、先从“树”开始回忆我们之前学过树。例如A / \ B C / \ D E这是一棵树。树有几个非常重要的特点特点1所有结点连通从A可以到B、C、D、E。特点2没有环不存在A → B → C → A这样的回路。特点3n个结点的树有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例如顶点数生成树边数2132435410910099这个结论是CSP-J初赛非常值得记忆的公式。七、为什么不能少于n−1条边假设有A B C D4个城市。如果只有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-B10 A-C2 B-C3如果选择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如果三条边都是1A-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-B4 A-C1 B-C2 B-D5 C-D3第一步按道路价格从小到大排序。得到1A-C 2B-C 3C-D 4A-B 5B-D然后从前往后看。选择1A-C可以A —— C选择2B-C可以A —— C —— B选择3C-D可以A —— C —— B | D现在4个顶点已经全部连通。我们已经选了4−13条边。结束总费用1236这就是一棵最小生成树。十八、为什么不选择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看点二十一、一个非常重要的考试对比KruskalPrim中文克鲁斯卡尔普里姆核心按边选择按点扩张又称加边法加点法起点不强调固定起点通常从一个顶点开始核心操作从小到大选边找连接当前集合的最小边关键条件不能成环加入一个新顶点最终n−1条边n个顶点全部加入经典复杂度与适用场景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费用11 2这是最短路径而最小生成树也是A —— B —— C费用112这里刚好一样。但是它们不是同一个问题。以后我们会专门学习最小生成树和最短路径不能混为一谈。二十四、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−119练习2一个连通图有8个顶点。它的任意一棵生成树有多少条边8−17练习3下面哪个是最小生成树的正确描述A. 边数最少的树B. 顶点数最少的树C. 权值总和最小的生成树D. 权值最大的生成树答案C练习4Kruskal算法的基本思想是什么回答按照边权从小到大选择边但是不能形成环。完全正确。三十四、给大家留一道思考题看下面的图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程序的算法。