最小生成树这个知识点，我在带新人刷408真题的时候发现一个特别有意思的现象：很多人能把Prim和Kruskal的代码背得滚瓜烂熟，但一到具体题目里给出一个带权图，问他“这题该用哪个算法”“为什么这里选错了边”“这个图是不是根本连不通”，立刻就卡壳。问题不在于他们没记住算法，而在于没真正理解最小生成树要解决的是什么问题、两种算法各自的适用边界在哪里。这篇内容我就围绕最小生成树这个考点，把王道408里涉及的核心概念、两种经典算法的实现细节、手算模拟过程、以及刷题时最容易踩的坑，从头到尾捋一遍。不管你是刚开始复习数据结构的小白，还是已经刷过一轮但做题正确率不稳的老选手，应该都能从里面找到对自己有用的东西。
1. 最小生成树到底在解决什么问题
1.1 从一个生活场景理解生成树的本质
先别急着看定义。想象你所在的城市有若干个小区，供电局要给这些小区铺设电缆。任意两个小区之间都可以铺线，但距离不同、施工成本不同。供电局的目标是用最低的总成本把所有小区都连通起来——注意，是“连通”，不是“两两直连”。只要任意两个小区之间能通过若干段电缆间接到达就行。
这个场景里，小区就是图的顶点，小区之间可铺设的电缆就是边，施工成本就是边的权值。供电局要的方案，本质上就是从一个带权无向图中选出一组边，使得所有顶点保持连通，同时选出的边权值总和最小。这组边构成的子图，就是最小生成树（Minimum Spanning Tree，简称MST）。
这里有几个关键点需要掰开说。第一，生成树必须包含图中全部顶点，一个都不能少。第二，选出的边必须保证图连通，不能有孤立的小团体。第三，选出的边数恰好是顶点数减一，因为一棵有n个顶点的树恰好有n-1条边，多一条就会成环，少一条就不连通。第四，在所有满足前三条的方案里，边权总和最小的那个才叫“最小”。
注意：最小生成树的前提是图本身是连通的。如果原图不连通，那就不存在生成树，只能求“最小生成森林”，每个连通分量各求一棵。408选择题里偶尔会拿这个做文章，给你一个不连通的图问最小生成树是否存在，答案是不存在。
1.2 最小生成树的性质：为什么贪心能work
很多人学完Prim和Kruskal之后会有个疑问：这两个算法都是贪心的，每一步都选当前看起来最优的边，凭什么贪心到最后就能得到全局最优？这背后其实依赖最小生成树的一个核心性质，叫做切分性质（Cut Property）。
用大白话说：把图的顶点分成两个不相交的集合，横跨这两个集合的边里，权值最小的那条边，一定属于某棵最小生成树。这个性质是整个贪心策略成立的基石。Prim算法每次把“已在树中的顶点集合”和“尚未加入的顶点集合”做一个切分，选横跨切分的最小边；Kruskal算法则是按权值从小到大考虑每条边，本质上也是在不断做切分判断。两种算法形式不同，但都踩在同一个性质上。
还有一个常考的性质是环性质：对于图中任意一个环，环上权值最大的那条边一定不属于最小生成树（严格说是“一定不存在于某棵最小生成树中”更准确，因为可能存在权值相同的多条最大边）。这个性质在做选择题判断“某条边是否可能属于最小生成树”时特别好用。
我个人的经验是，把这两个性质记牢，比死记算法步骤有用得多。很多408的选择题根本不需要你完整跑一遍算法，直接拿切分性质或环性质就能秒判。
1.3 最小生成树唯一吗：一个高频易错点
这是王道408里反复强调、也是考试特别爱设陷阱的地方。结论是：最小生成树的权值总和一定唯一，但树本身不一定唯一。
什么时候唯一？当图中所有边的权值互不相同时，最小生成树是唯一的。因为每一步贪心选择都没有并列选项，选法被完全确定。什么时候不唯一？当图中存在权值相同的边，且这些边在贪心过程中产生了“二选一”的局面时，就可能有多棵不同的最小生成树。
举个具体例子：一个三角形，三条边权值分别是1、1、2。你要连通三个顶点只需要两条边，显然选两条权值为1的边，总权值为2。但这两条权值为1的边具体是哪两条？其实三条边里任意两条权值为1的边……等等，这里只有两条权值为1的边，所以选法唯一。换个例子：正方形四个顶点，四条边权值都是1，两条对角线权值都是2。最小生成树选三条权值为1的边，但正方形有四条边，去掉任意一条都能得到一棵生成树，所以共有四种不同的最小生成树，权值总和都是3。
提示：考试里问“最小生成树是否唯一”，先看有没有等权边，再看等权边是否构成可替换关系。不要一看到等权边就说不唯一，也不要一看到权值全不同就放松警惕——权值全不同确实唯一，这是充分条件。
2. Prim算法：从顶点出发的“生长式”策略
2.1 Prim的核心思想与执行流程
Prim算法的思路非常直观：维护一个“已经加入树的顶点集合”，初始时随便挑一个顶点放进去，然后每一步都从“连接树内顶点和树外顶点”的所有边中，挑权值最小的那条，把它连接的树外顶点拉进树里，同时把这条边加入结果。重复这个过程，直到所有顶点都进树。
用一个类比：把已加入的顶点集合想象成一个不断扩张的“领地”，每一步都从领地边界上找一条最便宜的通道，把领地外最近的一个据点吞并进来。领地从一个点开始，逐步长大，最终覆盖全图。
具体执行步骤我拆成下面这个流程，手算时照着走不会乱：
- 任选一个起始顶点v0，加入集合U（U表示已在树中的顶点），结果边集TE初始为空。
- 在所有“一个端点在U内、另一个端点在U外”的边中，找权值最小的边（若有多条同权，任选一条，这正是不唯一的来源）。
- 把这条边加入TE，把它的U外端点加入U。
- 重复步骤2和3，直到U包含全部顶点。
这里有个细节很多人手算时会忽略：每加入一个新顶点后，候选边集合会扩大，因为新顶点又带来了若干条通往树外的新边。所以每一步都要重新在“当前所有跨界边”里找最小，而不是只在上一轮的候选里挑。我见过有同学手算时只盯着初始顶点连出去的边，加完一个点就不知道下一步该看哪些边了，这就是没理解“候选集动态扩张”这个点。
2.2 手算模拟：一步步走一遍
拿一个具体的图来跑。假设有5个顶点A、B、C、D、E，边和权值如下：
- A-B: 2，A-C: 3，A-D: 1
- B-C: 4，B-D: 5
- C-D: 6，C-E: 7
- D-E: 8
从A开始。U={A}，候选边是A-B(2)、A-C(3)、A-D(1)，最小是A-D(1)，选它，D入U。此时TE={A-D}，U={A,D}。
候选边更新：原来剩下的A-B(2)、A-C(3)，加上D带来的B-D(5)、C-D(6)、D-E(8)。最小是A-B(2)，选它，B入U。TE={A-D, A-B}，U={A,B,D}。
候选边：A-C(3)、B-C(4)、C-D(6)、D-E(8)、B-D(5)。最小是A-C(3)，选它，C入U。TE={A-D, A-B, A-C}，U={A,B,C,D}。
候选边：C-E(7)、D-E(8)。最小是C-E(7)，选它，E入U。TE={A-D, A-B, A-C, C-E}，总权值1+2+3+7=13。
验证一下边数：5个顶点选了4条边，符合n-1。连通性也没问题。这棵树的权值是13。你可以试试从别的顶点出发，比如从C开始，最终得到的权值一定也是13（权值唯一），但选出的边可能不同（如果过程中遇到等权边）。
2.3 Prim的复杂度分析与适用场景
Prim算法的时间复杂度取决于你怎么实现“找最小跨界边”这个操作。如果用最简单的邻接矩阵加一个数组记录每个顶点到当前树的最小距离，复杂度是O(n²)，n是顶点数。这个实现方式跟Dijkstra算法几乎一模一样，只是距离更新的含义不同——Dijkstra更新的是“到源点的最短路径”，Prim更新的是“到当前树集合的最短边权”。
如果用二叉堆（优先队列）来维护候选边，复杂度可以降到O(E log V)，E是边数。但这里有个坑：用堆实现时，每次加入新顶点都要把它的所有邻边压入堆，堆里可能会有大量“过期”的边（端点已经在树内的边），需要额外判断。所以实际写代码时，堆优化的Prim在稠密图上反而不如O(n²)的朴素版本省事。
适用场景的判断很直接：Prim适合稠密图，也就是边数接近n²的图。因为O(n²)的复杂度和边数无关，边再多也不影响。反过来，Kruskal适合稀疏图，因为它要对边排序，边少的时候排序开销小。408选择题里经常给一个“边很稠密”或“边很稀疏”的描述让你选算法，记住这个对应关系就行。
实操心得：手算Prim的时候，我习惯画一个表格，列是顶点，每行记录“当前该顶点到树的最小边权”和“是通过哪条边连过来的”。每加入一个新顶点就更新这一行。这个方法比在图上反复找边清晰得多，尤其是顶点多的时候不容易漏。
3. Kruskal算法：从边出发的“合并式”策略
3.1 Kruskal的核心思想与并查集的作用
Kruskal算法的思路换了个角度：不去管顶点集合怎么扩张，而是把所有边按权值从小到大排好序，然后依次考察每条边——如果这条边的两个端点当前还不在同一个连通块里，就选它，把两个连通块合并；如果已经在同一个连通块里，说明选它会成环，直接跳过。考察完所有边，选出的边就构成最小生成树。
这个算法的关键在于“判断两个端点是否已在同一连通块”以及“合并两个连通块”这两个操作。用并查集（Union-Find）来实现，效率非常高。并查集的核心是两个操作：Find（找某个元素所属集合的代表元）和Union（合并两个集合）。判断两个端点是否同属一个集合，就是比较它们的Find结果是否相同。
并查集本身也有优化技巧，主要是路径压缩和按秩合并。路径压缩是在Find过程中把沿途节点直接挂到根上，让后续查找更快；按秩合并是Union时把矮树挂到高树下，避免树退化成链。两个优化都用上，单次操作的均摊复杂度接近常数。408考试一般不要求你写完整的并查集优化代码，但理解它的作用是必要的，因为Kruskal的效率很大程度上依赖并查集。
3.2 手算模拟：排序加并查集走一遍
还是用上面那个5顶点图，边列表按权值排序：
- A-D: 1
- A-B: 2
- A-C: 3
- B-C: 4
- B-D: 5
- C-D: 6
- C-E: 7
- D-E: 8
初始时每个顶点各自一个集合：{A}{B}{C}{D}{E}。
考察A-D(1)：A和D不同集合，选它，合并{A,D}。TE={A-D}。
考察A-B(2)：A在{A,D}，B在{B}，不同集合，选它，合并{A,B,D}。TE={A-D, A-B}。
考察A-C(3)：A在{A,B,D}，C在{C}，不同集合，选它，合并{A,B,C,D}。TE={A-D, A-B, A-C}。
考察B-C(4)：B和C现在都在{A,B,C,D}里，同集合，跳过（选它会成环A-B-C-A）。
考察B-D(5)：同理，同集合，跳过。
考察C-D(6)：同集合，跳过。
考察C-E(7)：C在{A,B,C,D}，E在{E}，不同集合，选它，合并全部。TE={A-D, A-B, A-C, C-E}。
此时已选4条边，等于n-1，可以提前结束。总权值13，和Prim结果一致。
注意这里有个可以提前终止的优化：一旦选出的边数达到n-1，就可以停了，不用把剩下的边都考察完。手算时这个技巧能省不少时间。
3.3 Kruskal的复杂度与稀疏图优势
Kruskal的时间开销主要在两块：一是对E条边排序，复杂度O(E log E)；二是对每条边做并查集操作，接近O(E)。总复杂度是O(E log E)，只和边数有关，和顶点数关系不大。
这就解释了为什么Kruskal适合稀疏图：边少的时候E log E很小。而Prim的O(n²)在稀疏图里反而浪费，因为n²可能远大于E log E。反过来，稠密图里E接近n²，E log E约等于n² log n，比Prim的n²大，所以稠密图用Prim更划算。
| 对比维度 | Prim | Kruskal |
|---|---|---|
| 核心策略 | 顶点扩张，每次选跨界最小边 | 边排序，每次选不成环的最小边 |
| 时间复杂度 | O(n²)（朴素）/ O(E log V)（堆优化） | O(E log E) |
| 适用图类型 | 稠密图 | 稀疏图 |
| 依赖的数据结构 | 邻接矩阵/邻接表+距离数组 | 边集数组+并查集 |
| 是否依赖起点 | 是，需指定起始顶点 | 否，全局按边权处理 |
| 处理不连通图 | 只能得到一个连通分量的生成树 | 自然得到最小生成森林 |
注意：表格里“处理不连通图”这一行是很多人忽略的点。Prim从某个顶点出发，如果图不连通，它只能覆盖起始顶点所在的连通分量，其他分量根本进不来。Kruskal则不同，它遍历所有边，每个连通分量内部都会各自形成一棵生成树，最终得到的是最小生成森林。这个差异在判断题里出现过。
4. 刷题实战：高频题型与避坑指南
4.1 选择题里的“秒判”技巧
408选择题里关于最小生成树的题目，大致分几类，每类都有对应的快速判断方法。
第一类是判断某条边是否一定/可能/一定不属于最小生成树。这类题优先用环性质：找到包含该边的环，如果该边是环上唯一的最大权边，那它一定不属于任何最小生成树；如果环上有和它同权的其他最大边，那它可能属于某棵最小生成树（因为可以替换）。用切分性质也能判：如果能找到一个切分使得该边是唯一最小跨界边，那它一定属于所有最小生成树。
第二类是给定图问最小生成树权值。这种题老老实实跑一遍Prim或Kruskal，手算时选哪个算法看图的稠密程度。稠密图跑Prim，稀疏图跑Kruskal，能省时间。算完记得检查边数是不是n-1。
第三类是比较两种算法在某张图上的执行结果。常见问法是“Prim从某点出发得到的边集和Kruskal得到的边集是否相同”。答案是：权值总和一定相同，边集可能不同（存在等权边时）。如果图里所有边权互异，那两种算法得到的边集也相同。
第四类是算法适用性判断。给你图的特征描述（稠密/稀疏、是否连通、是否有负权边），问该用哪个算法。这里要澄清一个常见误解：最小生成树算法对负权边是完全没问题的，因为MST只看边的相对大小，负权边照样能正常处理。负权边会影响的是最短路径算法（比如Dijkstra不能处理负权边），不是MST算法。这个点考试里设过陷阱。
4.2 代码实现中的易错细节
如果考试涉及算法填空或代码题，有几个细节特别容易出错。
Prim的朴素实现里，距离数组dist[]的初始化很关键。通常把起始点的dist设为0，其余设为无穷大。然后每轮选一个“未访问且dist最小”的顶点u，标记访问，再用u去更新它所有未访问邻接点v的dist：dist[v] = min(dist[v], weight[u][v])。注意这里更新的是“到树集合的最小边权”，不是累加路径长度，这跟Dijkstra有本质区别。我见过有同学写代码时顺手写成dist[u] + weight[u][v]，那是Dijkstra的写法，放到Prim里就错了。
Kruskal的易错点在并查集的Find实现。递归版路径压缩写起来简洁：
def find(parent, x): if parent[x] != x: parent[x] = find(parent, parent[x]) return parent[x]但要注意递归深度，顶点特别多时可能栈溢出，实际工程里可以改迭代版。考试手写代码一般顶点数不大，递归版够用。另一个易错点是边的存储：Kruskal需要把所有边存成一个列表再排序，所以用边集数组（或三元组列表）比邻接矩阵方便。如果题目给的是邻接矩阵，需要先转换。
还有一个隐蔽的坑：判断成环的条件。Kruskal里判断的是“两个端点Find结果是否相同”，相同则跳过。有同学写成“判断这条边是否已经在结果集里”，这是不对的，因为成环不一定是因为重复选了同一条边，而是因为选了一条连接两个已连通块的边。
4.3 常见问题速查表
| 问题现象 | 可能原因 | 排查与解决 |
|---|---|---|
| 手算Prim时中途不知道看哪些边 | 没理解候选集动态扩张 | 每加一个顶点，把它所有通往树外的边加入候选，重新找最小 |
| Kruskal选出的边数不足n-1 | 原图不连通 | 检查图是否连通，不连通只能得森林 |
| 两种算法算出的权值不同 | 计算错误或图不连通 | 重新核对每条选中边的权值，确认图连通性 |
| 判断某边是否属于MST时拿不准 | 没用好环性质/切分性质 | 找包含该边的环，看它是否为唯一最大边 |
| Prim代码写成了Dijkstra | 距离更新用了累加 | Prim更新的是单边权，不是路径累加 |
| 认为有负权边就不能求MST | 混淆了MST和最短路径 | MST对负权边无限制，正常处理 |
| 等权边存在时误判MST唯一 | 把“权值唯一”和“树唯一”混淆 | 权值总和唯一，树本身可能不唯一 |
实操心得：做手算题时，我强烈建议在草稿纸上把每一步的“已选边集”和“当前候选边”都写清楚，别只在脑子里过。尤其是Prim，候选边每步都在变，写下来一目了然。Kruskal则建议把排序后的边列表列出来，选中的打勾、跳过的打叉并注明原因（成环），复查时一眼就能看出哪步出了问题。
4.4 一个容易被忽略的延伸考点
王道408在最小生成树这一节，偶尔会延伸到最小生成森林和次小生成树的概念。最小生成森林前面提过，就是图不连通时每个分量各求一棵。次小生成树则是权值第二小的生成树（权值可以等于最小，但边集不同），这个在408里出现频率不高，但理解它的思路对加深MST性质的理解有帮助：次小生成树一定是最小生成树替换一条边得到的，替换的方式是在MST上加一条非树边形成环，然后去掉环上权值最大的另一条边。
另外，瓶颈生成树的概念有时会跟MST一起提。瓶颈生成树是使“最大边权”最小的生成树。有个重要结论：最小生成树一定是瓶颈生成树，但瓶颈生成树不一定是最小生成树。这个结论在判断题里出现过，值得记一下。
我在实际带人复习的过程中发现，最小生成树这一块真正的难点从来不是算法本身有多复杂，而是那些边边角角的性质判断和适用场景的辨析。把Prim和Kruskal的代码背下来只要半小时，但要把环性质、切分性质、唯一性判断、连通性影响这些点全部吃透，需要反复在具体题目里磨。我的建议是，每做完一道MST的题，不管对错，都回头问自己一句：这道题考的是哪个性质？我是靠背结论做对的，还是真的推出来的？如果是背的，那就把推导过程补一遍。这个习惯坚持下来，这一块的题基本就不会再丢分了。
