最小生成树：Prim 与 Kruskal

在带权无向图里，有一类非常经典的问题：

如果要把所有顶点连起来，同时总代价尽可能小，应该怎么选边？

这类问题在现实里非常常见。比如：

修建通信网络，希望总布线成本最低；
铺设道路、电网，希望连接所有站点但尽量省钱；
做聚类或骨架连接时，希望先抓住最低代价的连接关系。

最小生成树，简称 MST，就是对这类问题的标准抽象。它并不关心某两个点之间的最短路径，也不要求保留图中所有边，而是只想从原图中挑出一部分边，使得：

所有顶点仍然连通；
没有环；
总权值最小。

而解决这个问题最经典的两种算法，就是 Prim 和 Kruskal。它们风格完全不同，一个更像“从一个点出发向外扩张”，一个更像“从全局最小边开始不断并边”，但最终目标是一致的。

一、什么是生成树

在一个连通无向图中，如果选出若干条边，使得：

能把所有顶点连起来；
并且没有形成环；

那么这些边构成的子图就叫原图的一棵生成树。

生成树有一个非常关键的性质：

如果图有 n 个顶点；
那么任意生成树都恰好有 n - 1 条边。

因为：

少了会不连通；
多了就会出现环。

二、什么是最小生成树

如果图是带权的，那么不同生成树的总代价可能不同。总权值最小的那棵生成树，就叫最小生成树。

所以 MST 的本质目标非常明确：

在所有可能的生成树中，找出边权和最小的一棵。

注意它解决的是“连通所有点的最小总代价”，而不是“任意两点之间最短路径”。这两个问题很容易混，但本质不同。

三、为什么最小生成树不等于最短路径树

这是必须先分清的一点。

1. 最短路径树

强调从某个源点到其他点的路径最短。

2. 最小生成树

强调把整个图连起来的总成本最小。

也就是说：

最短路径树优化“从一个点出发”的路径长度；
最小生成树优化“整体连通”的总边权和。

它们目标不同，所以结果也不一定相同。

四、Prim 算法的核心思想是什么

Prim 可以理解成一种“逐步扩展连通块”的算法。

它的基本思路是：

先从任意一个顶点开始；
当前已选顶点形成一个连通集合；
每次从“集合内部到集合外部”的所有候选边中，选权值最小的一条；
把这条边和对应的新顶点加入生成树；
重复直到所有顶点都被加入。

这很像“从一个点开始，慢慢向外长出一棵最便宜的树”。

五、Prim 为什么常和堆 / 优先队列一起出现

因为在 Prim 过程中，你需要反复做一件事：

在所有当前可扩展边中，快速找到权值最小的一条。

这和优先队列的能力高度吻合。

于是高效实现时，通常会：

用最小堆维护候选边或候选顶点；
每次取出当前代价最小的扩展选择；
再更新新的邻接边。

这说明前面学堆和优先队列，在图算法里又一次派上了用场。

六、Kruskal 算法的核心思想是什么

Kruskal 的风格和 Prim 很不一样。它更像一种“全局挑边”的算法：

先把所有边按权值从小到大排序；
依次考虑每一条边；
如果这条边连接的两个顶点当前还不连通，就把它加入生成树；
如果会形成环，就跳过；
重复直到选出 n - 1 条边。

可以把它想成：

从最便宜的边开始，能用就用，直到把所有顶点连成一棵树。

七、Kruskal 为什么常和并查集一起出现

因为在 Kruskal 过程中，最关键的判断是：

当前这条边的两个端点是否已经在同一个连通块中；
如果已经同组，再加这条边就会成环；
如果不在同组，就可以安全合并。

这正是并查集最擅长的问题：

判断是否同组；
动态合并集合。

所以 Kruskal 的经典实现几乎天然会使用并查集。

八、Prim 和 Kruskal 的本质差别是什么

可以先用一句话概括：

Prim 是“长点”，Kruskal 是“挑边”。

更具体地说：

1. Prim

从一个顶点出发；
维护一个不断扩展的连通块；
每次加一个新顶点。

2. Kruskal

不关心从哪个点开始；
直接从全图边里挑最小边；
逐步把多个小连通块并起来。

所以它们虽然都基于贪心，但贪心视角不同。

九、Prim 和 Kruskal 分别适合什么图

1. Prim 更适合稠密图

尤其是结合邻接矩阵时，处理顶点扩展会比较自然。

2. Kruskal 更适合稀疏图

因为边数相对较少，排序成本可接受，再配合并查集效率很好。

当然这不是绝对规则，但作为直觉判断非常有帮助。

十、最小生成树为什么通常是贪心算法

无论 Prim 还是 Kruskal，本质上都在做“当前看起来最划算的选择”：

Prim 每次选当前最小的跨集合边；
Kruskal 每次选全局最小且不成环的边。

它们之所以成立，背后依赖的是最小生成树问题的贪心性质，例如切分性质和环性质。入门阶段你不一定要把这些证明细节全部吃透，但至少要知道：

这不是拍脑袋的局部最优；
而是有理论保证的局部选择。

十一、最小生成树的现实应用有哪些

1. 网络建设

通信网络、供电线路、道路铺设的最低成本连接。

2. 聚类算法

例如某些最小生成树聚类思路。

3. 图形和网格骨架提取

寻找低成本连接骨架。

4. 近似解和基础连接结构

在很多更复杂问题中，最小生成树也常是一个基础参考结构。

十二、学习 Prim 和 Kruskal 时最容易踩的坑

1. 把最小生成树和最短路径混淆

这是最常见的问题。

2. 不理解 Kruskal 为什么要判环

因为生成树必须无环。

3. 不理解 Prim 为什么每次只选跨集合最小边

因为选内部边没意义，选外部边才是在扩张树。

4. 不知道为什么 Kruskal 要配并查集，Prim 要配堆

其实这正体现了它们各自的算法核心。

总结

最小生成树的重要性，不只是因为它是一类经典图算法，而是因为它把“整体连通成本最小”这类现实问题抽象得非常准确。真正值得先建立起来的，是这些核心认识：

生成树是在连通无向图中选出一组无环且连通所有顶点的边；
最小生成树优化的是总权值，不是单源最短路径；
Prim 更像从一个点向外扩张，Kruskal 更像全局按边贪心挑选；
Prim 常和优先队列搭配，Kruskal 常和并查集搭配；
两者都利用了最小生成树问题的贪心性质；
真正学会 MST，不是背两套模板，而是知道问题是在问“最短路径”，还是在问“最低总代价连接”。

把这一篇理解透之后，后面再去学最短路径和关键路径时，你会更容易把不同图优化目标区分开：有的在算“最省总成本”，有的在算“从一点到另一点最快”，它们虽然都在图上，但问题本质完全不同。

参考资源：