★ FEATURED ARTICLE 1. 为什么我要写这篇Kruskal算法教程最小生成树这个问题我在实际项目里遇到过好几次。最早一次是给一个园区做网络布线方案当时需要把十几栋楼用光纤连起来每栋楼之间铺设成本不一样怎么选线路让总成本最低本质上就是最小生成树问题。后来做聚类分析、图像分割、甚至一些路径规划的场景又反复碰到它。Kruskal算法是我个人最偏爱的解法原因很简单思路直观代码好写配合并查集之后效率也足够能打。这篇教程面向的是刚接触图论算法、或者学过但一直没搞太明白的朋友。我会从最基础的概念讲起把Kruskal的每一步拆开揉碎然后给出一份注释拉满的完整代码实现。你不需要有很深的算法功底只要会基本的数组操作和递归就能跟着走下来。整篇内容我会尽量用大白话解释该给的图例、该算的复杂度、该避的坑一个都不省。先说清楚Kruskal到底解决什么问题。给定一张连通的无向带权图图里有n个顶点和m条边每条边有一个权值可以理解为修这条路的成本、距离、时间等。我们要从中选出n-1条边把所有顶点连成一棵树并且让这n-1条边的权值之和最小。这棵树就叫最小生成树Minimum Spanning Tree简称MST。Kruskal的核心思想只有一句话把所有边按权值从小到大排序依次尝试加入只要这条边不会和已选的边构成环就选它直到选够n-1条边为止。听起来是不是特别简单但魔鬼在细节里。怎么判断“会不会构成环”这是整个算法的关键也是新手最容易卡住的地方。答案就是并查集。下面我会一步步展开。2. Kruskal算法的核心思路拆解2.1 贪心策略为什么能workKruskal本质上是一种贪心算法。贪心算法的特点就是每一步都做当前看起来最优的选择不回头。很多人第一次学的时候会犯嘀咕每一步都选最小的边最后一定能得到全局最优吗会不会前面选错了后面就崩了这个担心是合理的因为贪心不是万能的。但Kruskal的贪心是有严格数学证明支撑的这里我用直觉的方式给你讲明白。假设全局最优解是T我们按照Kruskal的方式选出来的边集是K。考虑第一条产生分歧的边eKruskal选了它而T没选。因为Kruskal是按权值从小到大选的所以e的权值一定不大于T中对应的那条边。我们把e加入T必然会形成一个环然后从环里去掉一条权值不小于e的边得到的新树权值不会变大。也就是说我们总能把T调整成包含e的、权值不增的另一棵最优树。一步步调整下去最终T就能变成K说明K也是最优的。这个证明思路叫交换论证是贪心算法正确性证明的经典套路。提示理解这个证明不是为了应付考试而是让你在写代码的时候心里有底。知道为什么对才敢放心用。2.2 并查集判断环的利器现在来说核心问题怎么判断新加入的边会不会构成环。最朴素的想法是每次加入一条边后从某个端点出发做一次DFS或BFS看能不能回到另一个端点。如果能回到说明有环。但这样每加一条边就要遍历一次图时间复杂度直接爆炸。更好的办法是用并查集Union-Find。并查集维护的是一堆不相交的集合支持两种操作查找Find某个元素属于哪个集合合并Union两个集合。放到Kruskal的场景里每个集合代表一个已经连通的顶点分量。初始时每个顶点各自成一个集合。当我们考虑一条边(u, v)时用Find查一下u和v是不是在同一个集合里如果在同一个集合说明u和v已经连通了再加这条边就会成环跳过。如果不在同一个集合说明这条边能把两个连通分量合并起来选它然后Union(u, v)。并查集如果配合路径压缩和按秩合并两个优化单次操作的平均时间复杂度几乎是常数级别的具体来说是反阿克曼函数α(n)这个函数增长极慢n取宇宙中原子总数级别时α(n)都不超过5。所以实际用起来可以当成O(1)。2.3 算法整体流程梳理把上面的东西串起来Kruskal的完整流程是这样的读入n个顶点、m条边每条边存成(u, v, w)的三元组。把所有边按权值w从小到大排序。初始化并查集每个顶点的父节点指向自己。遍历排序后的边对每条边(u, v, w)查找u和v的根节点。如果根节点不同说明不构成环选中这条边累加权值合并两个集合已选边数加一。如果根节点相同跳过。当已选边数达到n-1时提前结束。如果遍历完所有边后已选边数仍小于n-1说明原图不连通不存在最小生成树。整个算法的时间复杂度由排序主导是O(m log m)并查集部分近似O(m α(n))合起来还是O(m log m)。空间复杂度是O(n m)主要花在存边和并查集数组上。3. 手把手代码实现与逐行注释3.1 数据结构定义我用C来写因为竞赛和工程里都常用而且语法清晰。先定义边的结构体和并查集需要的数组。#include bits/stdc.h using namespace std; // 边的结构体u和v是两个端点w是权值 struct Edge { int u, v, w; // 重载小于号方便后面直接对边数组排序 bool operator(const Edge other) const { return w other.w; } }; const int MAXN 100005; // 最大顶点数 int parent[MAXN]; // 并查集的父节点数组 int rnk[MAXN]; // 按秩合并用的秩数组这里用operator重载是为了后面能直接用sort对Edge数组排序省得再写比较函数。parent数组存每个节点的父节点rnk数组存每个集合的秩可以粗略理解为树的高度上界用于按秩合并优化。3.2 并查集的查找与合并并查集的两个核心操作我分开写注释给足。// 查找操作带路径压缩 int find(int x) { // 如果x不是根节点递归查找其父节点的根并把沿途节点的父节点直接设为根 if (parent[x] ! x) { parent[x] find(parent[x]); // 路径压缩的关键一行 } return parent[x]; } // 合并操作带按秩合并 bool unite(int x, int y) { int rx find(x); int ry find(y); if (rx ry) return false; // 已经在同一个集合合并失败 // 把秩小的树挂到秩大的树下面保持树尽量矮 if (rnk[rx] rnk[ry]) { parent[rx] ry; } else if (rnk[rx] rnk[ry]) { parent[ry] rx; } else { parent[ry] rx; rnk[rx]; } return true; }路径压缩那一行parent[x] find(parent[x])是整个并查集效率的灵魂。它把查找路径上所有节点的父节点直接指向根下次再查这些节点就是一步到位。按秩合并则是防止树退化成链。两个优化叠加效率拉满。注意路径压缩和按秩合并可以只用其中一个但两个都用效果最好。如果只写路径压缩代码更短实际性能也够用看你取舍。3.3 Kruskal主函数完整实现下面是主逻辑我把每一步都拆开注释。int main() { int n, m; cin n m; // 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()); // 第二步初始化并查集每个顶点自成一个集合 for (int i 1; i n; i) { parent[i] i; rnk[i] 0; } int totalWeight 0; // 最小生成树的总权值 int edgeCount 0; // 已选边数 // 第三步遍历所有边 for (int i 0; i m edgeCount n - 1; i) { int u edges[i].u; int v edges[i].v; int w edges[i].w; // 尝试合并u和v所在的集合 if (unite(u, v)) { // 合并成功说明这条边不构成环选它 totalWeight w; edgeCount; } // 合并失败说明构成环直接跳过 } // 第四步判断是否所有顶点都连通 if (edgeCount n - 1) { cout 最小生成树总权值: totalWeight endl; } else { cout 图不连通不存在最小生成树 endl; } return 0; }这份代码可以直接编译运行。输入格式是第一行两个整数n和m接下来m行每行三个整数u、v、w表示一条连接u和v、权值为w的边。输出是最小生成树的总权值或者提示图不连通。3.4 一个完整的输入输出示例光看代码可能还是有点虚我拿一个具体例子走一遍。假设有4个顶点、5条边4 5 1 2 1 1 3 4 2 3 2 2 4 5 3 4 3排序后的边是(1,2,1)、(2,3,2)、(3,4,3)、(1,3,4)、(2,4,5)。处理(1,2,1)1和2不在同一集合选总权值1合并{1,2}。处理(2,3,2)2在{1,2}3单独不在同一集合选总权值3合并{1,2,3}。处理(3,4,3)3在{1,2,3}4单独不在同一集合选总权值6合并{1,2,3,4}。此时已选3条边等于n-13提前结束。输出总权值6。你可以验证一下这确实是最小的。4. 实操中容易踩的坑与排查技巧4.1 常见错误速查表我在教别人和帮人debug的过程中总结出下面这些高频问题基本覆盖了90%的翻车场景。问题现象可能原因排查方法结果偏大排序写反了从大到小排检查比较函数或sort的用法结果偏小并查集查找没写路径压缩或者合并逻辑写错手动模拟小数据打印每次选边死循环find函数递归没写终止条件确认parent[x] x时返回数组越界顶点编号从0开始但数组从1初始化统一编号规范或数组开大一点图不连通误判边数不够但代码没检查最后判断edgeCount n-1权值溢出总权值用int存不下改用long long4.2 三个我亲自踩过的坑第一个坑是顶点编号问题。有些题目顶点从0开始编号有些从1开始。我刚开始写的时候没注意并查集初始化从1到n结果0号顶点没初始化parent[0]是随机值直接段错误。后来我养成了习惯看题先确认编号范围初始化的时候老老实实按范围来。第二个坑是提前终止条件写错。我见过有人写成edgeCount n结果永远选不够因为最小生成树只有n-1条边。还有人忘了在循环条件里加edgeCount n-1导致选够之后还在继续遍历虽然结果不错但浪费了时间。这个细节在小数据上看不出来数据量一大就明显了。第三个坑是重边和自环。有些图里存在自环u等于v或者重边两条边连接同样的两个顶点但权值不同。自环在Kruskal里会被并查集自动过滤掉因为u和v本来就在同一集合。重边也没问题排序后先处理权值小的大的自然被跳过。所以Kruskal天然能处理这两种情况不需要额外写代码。但如果你用其他算法比如Prim就得小心了。提示写完之后一定要拿小数据手动模拟一遍最好拿纸笔画一画。我见过太多人代码看着没问题一跑就错就是因为没手动验证。4.3 性能优化的几个实用技巧虽然Kruskal本身已经很快了但在极端数据下还是可以做些优化。第一用scanf/printf代替cin/cout或者加上ios::sync_with_stdio(false)输入输出能快不少。第二边数组用vector而不是固定数组避免开太大浪费内存或者开太小越界。第三并查集的find写成迭代版虽然递归版更简洁但数据量特别大时递归可能爆栈迭代版更稳。// 迭代版find避免递归爆栈 int find(int x) { int root x; while (parent[root] ! root) { root parent[root]; } // 路径压缩 while (parent[x] ! root) { int next parent[x]; parent[x] root; x next; } return root; }这个迭代版先找到根再把路径上所有节点直接连到根。逻辑比递归版绕一点但胜在安全。5. Kruskal与其他最小生成树算法的对比5.1 Kruskal vs Prim到底该用哪个这是新手最常问的问题。两个算法都能求最小生成树但适用场景不太一样。我做了个对比表对比维度KruskalPrim核心思想按边贪心按点贪心时间复杂度O(m log m)朴素O(n²)堆优化O(m log n)适用图类型稀疏图更优稠密图更优是否需要并查集需要不需要代码难度中等中等处理不连通图天然支持最后判断即可需要额外处理简单来说边少用Kruskal点多用Prim。比如一个图有1000个顶点但只有2000条边Kruskal的m log m大概是2000乘以11两万多Prim的n²是一百万差距明显。反过来如果图有1000个顶点、接近50万条边稠密图Kruskal要处理50万条边的排序而Prim用邻接矩阵是n²即一百万差不多但堆优化Prim是m log n也还行。实际做题时如果没特殊要求Kruskal因为思路简单、代码好写往往是首选。5.2 什么场景下Kruskal更香除了稀疏图还有几种情况Kruskal特别合适。一是边已经部分有序比如按某种规则生成时天然接近有序排序开销小。二是需要动态加边的场景Kruskal的并查集结构天然支持增量处理。三是需要求次小生成树或者最小瓶颈生成树的变种问题Kruskal的框架更容易改造。我在做网络布线方案时选Kruskal就是因为边数远小于顶点数的平方而且需要反复调整某些边的权值重新计算Kruskal改起来方便。注意如果图是稠密图且用邻接矩阵存储Prim可能更自然。但如果用邻接表两者差距不大看个人习惯。6. 从模板题到实际应用的跨越6.1 经典模板题变形解析很多在线评测平台都有最小生成树的模板题但实际题目往往会有变形。我举几个常见的变形一输出具体选了哪些边。这个最简单在选边的时候把边的编号或端点存下来就行。注意输出顺序有些题目要求按输入顺序输出有些按权值顺序看清楚。变形二判断最小生成树是否唯一。这个稍微绕一点。思路是在Kruskal过程中如果存在权值相同的边且替换后仍能得到同样总权值的生成树就不唯一。具体做法是对每一组权值相同的边先记录哪些边被选中然后看这些边能否用同权值的其他边替换。代码量会大一些但核心还是Kruskal。变形三求最小生成树的最大边权。这个更简单Kruskal选的最后一条边就是最大边权因为边是按从小到大选的。直接输出最后选中的那条边的权值即可。变形四图不连通时求最小生成森林。有些题目不要求全图连通而是要求每个连通分量内部各自求最小生成树。Kruskal天然支持遍历完所有边后每个连通分量都会有自己的最小生成树总权值就是所有分量权值之和。6.2 实际工程中的应用场景最小生成树不只是算法题实际工程里用得很多。我接触过的场景包括网络布线前面提到的园区光纤铺设每栋楼之间铺设成本不同求最小成本方案。电路设计芯片上引脚之间的连线希望总长度最短减少信号延迟和功耗。聚类分析把数据点看成顶点点之间的距离看成边权最小生成树去掉最长的几条边就能得到聚类。图像分割像素作为顶点相邻像素的相似度作为边权最小生成树可以帮助分割区域。路径规划在某些场景下需要以最小总代价连接多个目标点最小生成树提供基础方案。这些场景的共同点是需要连通所有节点同时总代价最小。只要满足这个特征就可以考虑最小生成树。6.3 扩展阅读与进阶方向如果你已经把Kruskal吃透了可以往这几个方向继续深入。一是次小生成树求权值第二小的生成树思路是先求最小生成树然后枚举替换一条边。二是最小树形图也叫有向图的最小生成树用的是朱刘算法比Kruskal复杂不少。三是斯坦纳树允许在图中增加额外的顶点来降低总权值是NP难问题通常用状态压缩DP求解。四是动态最小生成树支持边的插入和删除需要更高级的数据结构。这些进阶内容我后续会单独写文章展开这篇先把Kruskal的基础打牢。7. 我个人的一些实操心得最后分享几个我在实际写Kruskal时总结的小技巧都是文档里不会写的。第一并查集的初始化别偷懒。我见过有人只初始化用到的顶点结果其他顶点是随机值一查就崩。老老实实从1到n或者0到n-1全部初始化不差那点时间。第二排序前先确认边的存储方式。如果用结构体数组记得重载小于号或者传比较函数。如果用pair或者tuple注意默认排序规则是不是你想要的。我一般用结构体加重载最直观。第三提前终止的条件要写对。edgeCount n - 1这个条件放在循环里选够就停别傻乎乎遍历完所有边。数据量大的时候这点优化很可观。第四权值用long long。很多题目边权能到10的9次方n能到10的5次方乘起来就是10的14次方int根本存不下。我吃过这个亏后来一律用long long省心。第五多画图多模拟。算法这东西看十遍不如手动走一遍。拿张纸画几个点几条边按照代码逻辑一步步走比盯着代码看效率高得多。第六善用调试输出。在选边的时候打印一下选了哪条边、当前总权值多少跑小数据的时候一目了然。调通了再把输出删掉或者注释掉。这些经验看起来琐碎但都是实打实踩出来的。你如果刚开始学照着做能少走不少弯路。如果已经会了也可以对照检查一下自己有没有中招。Kruskal这个算法本身不复杂难的是把细节抠干净把边界情况都考虑到。多写几遍多调几次自然就熟了。
阅读完成 · 觉得有帮助？
