最小生成树算法详解：Kruskal与Prim的对比与实战

1. 为什么说最小生成树是竞赛图论里绕不开的坎如果只能选一个算法去整理竞赛图论的知识树我会把最小生成树放在最上层。蓝桥杯、ACM 的题单里最小生成树既是最经典的入口级模板也是理解“贪心策略”和“图的性质”的第一手教材。Kruskal、Prim 这两个名字凡是正经刷过洛谷的选手基本都绕不过去。我见过不少初学者背了模板能过题但对这两个算法到底各自擅长什么、瓶颈在哪、什么时候会翻车其实一知半解。等到换一道题比如加上“需要输出最小生成树的某条边”“图不连通怎么办”“边权有负数”就开始发慌。归根到底是因为没有真正吃透算法背后的贪心依据也缺乏对代码细节的敏感性。这篇文章不打算只贴一堆代码了事我更想从“为什么这样设计”的角度把 Kruskal 和 Prim 掰开揉碎结合洛谷 P3366 这个模板题把两个算法的完整结构、复杂度、适用场景、常见坑都讲清楚。看完以后你再遇到最小生成树问题至少能快速判断该用哪个算法也知道写代码时哪里容易踩雷。2. 先搞清楚最小生成树到底在求什么2.1 定义没那么玄乎就是“连起来且总边权最小”给定一个带权无向图如果它有 n 个顶点最小生成树就是从中选出 n-1 条边把这 n 个点全部连通并且让选出的边权总和尽量小。为什么是 n-1 条边因为一棵树有 n 个点时恰好需要 n-1 条边再多一条就会成环少一条就连不通。这个要求看似简单但“总边权最小”这个目标并不是随便贪心都能做到的。用生活化的例子来理解你在一个城市里规划自来水管网要把所有小区都接通连接两个小区之间的管道造价不同。最小生成树算法就是在所有可能的连接方案里挑一个总造价最低的方案。它不会去管两个小区之间“直达”是否最方便只关心整张网的总成本最低只要所有点连通就行。这个思路放到电路布线、通信网络、聚类分析里也都是同一套逻辑。2.2 为什么“局部最优”最后能拼成“全局最优”初学者最容易卡住的地方是问“凭什么每次选当前最小的边最后就一定没错”。这背后有两个图论中的经典性质切割性质和回路性质。切割性质说的是把点集任意分成两部分横跨这两部分的所有边里权值最小的那条一定出现在某个最小生成树里。Kruskal 每次选的是“不成环的最小边”Prim 每次选的是“连接已选点集和未选点集的最小边”本质上都跑不出这个逻辑。回路性质则是说如果一个回路里有一条边比同回路其他边都大那么它一定不属于最小生成树。kruskal 排序后从小到大加边一旦发现这条边会形成环路就直接跳过正是利用了回路性质把那些“多余的较大边”全部排除掉。这两个性质是理解 MST 的钥匙也是以后进阶做次小生成树、动态 MST 时反复使用的工具。2.3 模型延伸负权边、重边、自环要不要怕最小生成树的定义里并不要求边权为正负权边完全不慌算法照样能处理。因为它要的是“边权和最小”负权边反而是好事只要不成环能加上就加。重边也没问题结构上你只需要保留权值最小的那条边但实际代码里像 Kruskal 排序后自然就先处理小权重的边Prim 更新距离时也只取更小的那个所以重边会被自动忽略较大者。自环就更简单了它不可能帮助连通性Kruskal 用并查集判断会直接跳过Prim 里更新的时候对已访问点没有作用也天然忽略。3. Kruskal 算法排序加并查集的经典组合3.1 核心思想一句话把所有边排序从小到大挑能连就连Kruskal 是一个全局贪心的玩法。它根本不关心图的结构先把所有边按照权值从小到大排好然后用一个数据结构维护当前连通状态逐条边尝试加入。具体过程是这样的一开始我们手里有 n 个孤立的点相当于 n 个单独的集合。小时候到大的边依次来看如果这条边的两个端点目前不属于同一个集合说明加入它不会形成回路那就把这条边选进生成树并把两个集合合并。如果两个端点已经在同一个集合里说明这条路已经能通过其他选中的边连通再加反而成环直接放弃。当选中了 n-1 条边时最小生成树就构建完成。3.2 并查集为什么是绝配这里需要“快速判断两个点是否连通”和“快速把两个连通块合并”的数据结构并查集几乎是为这个场景量身定做的。基础的并查集加上路径压缩和按秩合并这两个优化后单次查询和合并的均摊复杂度接近常数级别比赛里完全可以当作无脑工具来用。大家最熟悉的是递归版 find 函数int find(int x) { return fa[x] x ? x : fa[x] find(fa[x]); }路径压缩会在递归返回时把沿途的节点直接指到根上下一次再查就一步到位。有人担心递归深度会不会爆栈其实由于路径压缩的存在正常数据下深度不会超过几层竞赛环境里完全不用焦虑。如果你实在不放心也可以写迭代版但这在 Kruskal 里不是瓶颈。合并的时候有个小细节常规写法是直接fa[ra] rb但这会退化到链状的深度。加一个按秩合并维护一个rnk数组表示根节点的深度永远把深度小的根挂到深度大的根下面整个平衡性会好很多。在数据随机的情况下差别不大但遇到刻意构造的数据时按秩合并能有效避免退化。3.3 标准 C 实现与复杂度分析以洛谷 P3366 为例边用结构体存储排序用sort的默认顺序所以直接重载小于号即可。完整代码如下#include bits/stdc.h using namespace std; struct Edge { int u, v, w; bool operator (const Edge other) const { return w other.w; } }; vectorint fa; int find(int x) { return fa[x] x ? x : fa[x] find(fa[x]); } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, m; cin n m; vectorEdge edges(m); for (int i 0; i m; i) { cin edges[i].u edges[i].v edges[i].w; } sort(edges.begin(), edges.end()); fa.resize(n 1); for (int i 1; i n; i) fa[i] i; long long ans 0; int cnt 0; for (int i 0; i m; i) { int ru find(edges[i].u); int rv find(edges[i].v); if (ru ! rv) { fa[ru] rv; ans edges[i].w; cnt; if (cnt n - 1) break; } } if (cnt n - 1) cout ans \n; else cout orz\n; return 0; }时间复杂度很好分析排序是 O(m log m)并查集处理 m 条边基本算作 O(m·α(n))α 是可忽略的增长极慢的函数。综合起来Kruskal 的复杂度就是 O(m log m)和顶点数关系不大主要被边的数量支配。空间复杂度是 O(m n)存储边和并查集数组。这个算法写起来简单而且当图很大、边很多时只要内存能放下边数组跑起来都很快。3.4 这里有个判断连通性的细节值得反复确认很多人写 Kruskal 到一半最后直接输出 ans 就收工忘记了“图可能不连通”这个条件。当图本身不是连通图时选不出 n-1 条边这时应该输出“orz”。判断方法就是在循环结束后检查一下 cnt 是不是等于 n-1。我在洛谷 P3366 的题解区见过太多第一次提交 WA 的代码原因无外乎是没判连通性或者把 cnt 的位置放错了。cnt 的递增时机必须跟“成功合并且加入边”绑定不能是“遍历了一条边”就加一。这个逻辑要形成条件反射写的时候顺手把 if 判断加上别赌数据里一定有解。4. Prim 算法从一个点长出一棵树4.1 和 Kruskal 的视角完全反过来Kruskal 是从边的角度出发Prim 则是从点的角度出发。它从任意一个起点开始维护一个“已经长出来的大树”每一步都从“连接树内点到树外点的所有边”里挑一条最短的把新的树外点拉进树里然后继续重复。为什么每次挑最短的跨界边是对的呢这正好对应前面说的切割性质。当前树内的点看作点集 A树外的点看作点集 B横跨这两个集合的所有边中权值最小的那条一定属于某个最小生成树。Prim 每一次都是无损的贪心所以最终能得到全局最优解。4.2 朴素版和堆优化版的差别如果图是用邻接矩阵存储的稠密图朴素 Prim 的实现非常经典维护一个dist数组记录每个未确认点到当前树的最短距离每一轮扫描全部点找出距离最小的那个加入树再用它的所有出边更新其余点的距离。这个过程每轮是 O(n)一共 n 轮总复杂度 O(n²)。如果是稀疏图比如洛谷 P3366 里 m 远小于 n² 的情况用邻接表加优先队列来做堆优化 Prim 更加合适每次从队头取出当前距离最小的点如果它已经在树里就跳过否则加入树然后通过邻接表把新的可能更小距离压进堆。堆优化版本的复杂度是 O(m log n)。4.3 堆优化版完整代码还是以 P3366 为例我用priority_queue实现小根堆注意 pair 的排序逻辑是把权重放 first#include bits/stdc.h using namespace std; struct Edge { int to, w; }; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, m; cin n m; vectorvectorEdge g(n 1); for (int i 0; i m; i) { int u, v, w; cin u v w; g[u].push_back({v, w}); g[v].push_back({u, w}); } const int INF 0x3f3f3f3f; vectorint dist(n 1, INF); vectorbool inTree(n 1, false); priority_queuepairint, int, vectorpairint, int, greaterpairint, int pq; dist[1] 0; pq.push({0, 1}); long long ans 0; int cnt 0; while (!pq.empty()) { auto [d, u] pq.top(); pq.pop(); if (inTree[u]) continue; inTree[u] true; ans d; cnt; for (auto e : g[u]) { if (!inTree[e.to] e.w dist[e.to]) { dist[e.to] e.w; pq.push({e.w, e.to}); } } } if (cnt n) cout ans \n; else cout orz\n; return 0; }这段代码里有几个细节很容易写错。第一个是priority_queue的小根堆写法默认是最大堆所以要加上greaterpairint, int而且 pair 的 first 必须是边权否则排序就乱套了。第二个是dist数组的含义它不是某个点相对起点的最短路径而是相对“当前已生成树”的最短距离。所以当新点被加入树后用它的出边去更新别的点时只取e.w dist[e.to]。第三点的加入顺序里会存在重复的陈旧堆元素所以if (inTree[u]) continue;是必备过滤不是可选项。4.4 嵌套复杂度对比稠密图里朴素版反而更强堆优化 Prim 看起来更高级但实际上在完全图那种稠密场景朴素版 O(n²) 反而更可靠。堆优化版在边数接近 n² 的完全图里复杂度的常数更大、堆操作也更多常常跑不过朴素版。这是很多人的认知盲区一看到堆就觉得天下无敌结果在稠密图数据上被朴素 Prim 吊打。5. Kruskal 和 Prim 怎么选关键时刻别犹豫5.1 一张表看穿两个算法的优劣势我用一张表把核心差异列出来比赛时扫一眼就能定位比较维度KruskalPrim堆优化Prim朴素版核心操作对边排序 并查集优先队列 邻接表循环扫描点 邻接矩阵时间复杂度O(m log m)O(m log n)O(n²)擅长场景稀疏图、边数少稀疏图但点也很多稠密图、完全图代码难度低逻辑直白中堆细节多低但空间占用大处理重边自动取小自动取小取小存入矩阵即可是否依赖起点不依赖依赖但不影响结果依赖但不影响结果内存占用存边为主O(m)邻接表O(nm)邻接矩阵O(n²)什么时候选 Kruskal只要边数是几十万以下、你能把所有边读进内存Kruskal 永远是稳妥的第一选择。实现简单、不容易写错、调试也快比赛里时间宝贵能少费心思就少费心思。什么时候选 Prim 堆优化图稀疏但顶点数量极其巨大比如 n 到十万级别、m 也很大Kruskal 需要对 m 条边排序也还行实际上这两种往往性能接近。Prim 更占优势的场合是边数相对 n 不太大的稠密图之外的特殊场景或者你已经在维护优先队列有其他便利。什么时候选朴素 Primn 在几千级别同时 m 接近 n²比如完全图的最小生成树问题。此时 O(n²) 远比 O(m log m) 香因为 m 已是百万级排序就够吃一壶。5.2 蓝桥杯/ACM 的实际选择策略以洛谷 P3366 的数据规模来说顶点数和边数往往设置为 n 最多几千、m 最多二十万的级别两种算法都能轻松跑过。你在蓝桥杯的填空题、程序设计题里可能遇到 n1000、m100000 的稀疏图也可能遇到 n2000 且边接近全连接的稠密图。我的建议是平时把 Kruskal 当作默认主力因为它写着最轻松正确性也最容易确认。遇到 n 很小两千以内且边很密的题目就切换到朴素 Prim。至于堆优化 Prim也要熟练掌握因为有的题目需要借助 Prim 的思路来扩展比如求最小生成树过程中维护某个最大值之类的变体Kruskal 就不如 Prim 灵活。5.3 一个我记得很清楚的反面教训有一次我刷题遇到一个最大生成树问题想都没想就套了 Kruskal 模板。排序函数写的是升序然后我自作聪明把排序改成降序并查集部分照旧结果样例过了交上去却 WA。后来发现我忽略了一个细节最大生成树依然要“不成环”但相同权重下选边顺序会影响最终生成树的形态如果不处理重边就会选出重复的不合法方案。其实解法本身没问题问题出在审题没看清楚把“要求输出方案中某条边的编号”给漏了。所以说算法是死的题目是活的模板背得再熟也得先读清楚题面要求。6. 洛谷 P3366 模板题完整冲关6.1 题目到底要我们做什么P3366 是最标准的最小生成树模板题。输入第一行给出 n点数和 m边数接下来 m 行每行三个整数 u、v、w表示一条无向边。题目要求求出这个图的最小生成树边权之和如果图不连通也就是无论怎么选都不可能产生包含全部 n 个点的树就输出 orz。这个题的考点非常纯粹一是检验你是否真的理解 MST 的构建流程二是检验边界条件处理是否周全。很多人模板背得滚瓜烂熟结果 WA 在“不连通输出 orz”这个点上。6.2 用 Kruskal 逐步拆解答题过程第一步读入 n 和 m建一个边数组。数据量大时一定记得打开ios::sync_with_stdio(false)和cin.tie(nullptr)别让 IO 拖后腿。第二步初始化并查集。这里要注意下标从 1 开始所以fa要开 n1 大小循环把fa[i]i。第三步排序。直接用sort(edges.begin(), edges.end())前提是结构体重载了按权值排序的运算符。第四步遍历边进行并查集合并。记录两个关键的变量ans存权值总和cnt存已经加入的边数。一旦cnt n - 1就立即 break后面边不用再看了。这个是常规优化因为 MST 已经生成完毕。第五步输出判断。如果cnt n - 1输出 ans否则输出 orz。全过程非常线性我强烈建议初学者先把 Kruskal 从理解到代码全部吃透因为它基本覆盖了“贪心 排序 并查集”这三个竞赛基本功。6.3 用 Prim 解题时同样要盯住连通性Prim 代码里cnt 在这里表示已经加入树中的顶点个数。如果图是连通的跑完优先队列cnt 会恰好等于 n。如果图不连通cnt 会小于 n这时候就输出 orz。很多人会把 Prim 的 cnt 和 Kruskal 的 cnt 搞混Kruskal 里是边数Prim 里是点数但最终判断连通性的标准是统一的Kruskal 看 cnt 是否等于 n-1Prim 看 cnt 是否等于 n。写代码前先想清楚自己在数什么这是最容易自测的一个点。6.4 测试用例怎么构造自己本地测试时至少要覆盖这几种情况普通连通图、有重边的图、有自环的图、不连通的图、两个点的图以及 n1 这种极端情况。当 n1 时最小生成树不需要任何边Kruskal 里 cnt 初始为 0 恰好等于 n-1输出 0Prim 里 cnt 初始为 1输出 0。这个边界很容易让人另写特判但其实这两个算法在正确实现下根本不需要特判挺奇妙的。举个简单的不连通样例3 2 1 2 5 2 3 7这时候点 1 和点 2、点 3 连通但整个图显然连通所以答案 12 没问题。真不连通就改成3 1 1 2 5第 3 个点是孤立的答案输出 orz。拿这两组测试一跑就能检测连通性判断是否写对。7. 实战经验、常见坑与调试技巧7.1 我踩过的五个高频坑并查集忘记初始化。这个坑听起来低级但确实很常见尤其是把代码写到类里时容易漏。初始化要放在fa.resize(n1)之后并把 1 到 n 全部赋值为自己。边数组开太小。有的题目边数 m 给得很暧昧比如虽然没有说明是多组数据但实际存在多组输入如果你按单组数据的大小开数组就可能越界。稳妥做法是尽量用 vector 动态分配不要用固定数组。忘记用 long long。P3366 的边权数据虽然不会超 int但总和可能会接近 int 上限尤其在一些综合题里边权和可能大得吓人。竞赛里只要涉及“求总和”我一律用 long long这个习惯能帮你避免不少隐藏的 WA。优先队列没写greater。这个问题我犯过不止一次。一旦忘了写堆变成大根堆Prim 就会优先处理最远的点程序会变成“最大生成树”如果正好遇到数据让你误打误撞输出正确结果那更是灾难。更新 dist 时忘记判断!inTree[e.to]。其实不判断也不一定会错因为如果点已经在树里它不会再次被加入。但少了这层判断会让堆里出现很多无用的更新浪费时间和内存而且逻辑上也不严谨还是写上。7.2 一些从实战里沉淀出来的调试技巧本地测试的时候与其指望一次样例通过不如构造一个已知答案的小图然后手算一遍。比如一个简单的三角形图3 3 1 2 1 2 3 2 1 3 3正确答案是 123。Kruskal 排序后依次处理 1、2、3边权为 3 的那条因为会成环被跳过。Prim 从 1 出发距离 1 的点是 2加入后更新点 3 的距离为 2最终也得到 3。两组代码都能跑出 3 的话基本可以确认主线逻辑没问题。我还会在代码里临时输出 cnt 和每个被选中的边这样一旦答案不对立刻能看出是连通性判断错了还是选边逻辑错了。比赛时临时输出的调试信息要记得删掉或者用#ifdef LOCAL包起来不然交上去可能因为多余输出直接 WA那是最冤的。7.3 算法上再做一点延伸思考学会了 Kruskal 和 Prim接下来可以顺手练几个常见变形最大生成树、次小生成树通常用 Kruskal 先求 MST再枚举非树边换边、生成树计数、有向图的生成树问题等。Kruskal 在“生成树 并查集”这个组合下特别容易扩展比如判断图是否连通、求连通块数量、动态加边维护 MST 等。Prim 则在需要利用“当前树到任意点最小距离”的题意中更顺手比如带点权的生成树、限定起点的生成树变体或者与最短路思想结合的时候。两类算法不是二选一的互斥关系而是互补的技能点能顺手都写出来才算真正过关。8. 关于这两个算法的最后几句心里话刷了很多图论题之后我最大的体会是模板题的意义不在于让你背代码而是让你在写代码的过程中把“贪心证明”和“数据结构能力”揉在一起。Kruskal 训练的是排序和并查集的连招Prim 训练的是堆和动态更新的敏感度。你每写一遍都会对这些工具更熟悉。最后再分享一个小习惯我每次准备比赛前会把 Kruskal 和 Prim 的模板各默写一遍不查资料重点检查并查集初始化和优先队列细节顺带把边界用例过一下。几次之后这些代码就彻底长在脑子里了。做模板题不只是为了 AC而是为了在真正的赛场上做到“肌肉记忆式的稳定”这恰恰是蓝桥杯和 ACM 最看重的能力。