Kruskal算法详解：C语言实现最小生成树的贪心与并查集技巧

1. 从连通所有站点说起Kruskal算法到底在解决什么问题先说一个很实际的需求场景假设你是某个乡镇的网络布线负责人手里有N个村子的接入点乡镇府批了一笔光纤铺设预算要求把N个村子全部接入主干网同时光纤总里程必须最短。村子之间有些山梁、河沟和现有道路不同路段的铺设成本差异很大怎么选线才能既保证所有村子连通又把总成本压到最低这类问题在计算机科学里有一个规范的名字——最小生成树Minimum Spanning Tree, MST。它的定义很直白在一个带权无向图中找出一个包含全部N个顶点、由N-1条边构成的连通子图并且这N-1条边的权值之和最小。如果这个图是疏的即边数远小于顶点数的平方那么Kruskal算法几乎是最直观、最容易用C语言手写的解法之一。Kruskal算法的核心思想用一句话概括就是贪心 并查集。先把所有边按权值从小到大排序然后从最小的边开始逐条尝试加入生成树的边集每次加入前判断一下——如果这条边的两个端点已经在同一个连通块里就放弃它否则就把它纳入结果集并合并这两个端点所在的连通块。循环直到选够了N-1条边为止。这个算法之所以值得拿出来单独写一篇C语言实现的文章不光是因为它逻辑清晰更因为在具体编码时你会遇到好几个纸上谈兵容易、落地实现踩坑的细节并查集的路径压缩怎么写才不容易出错、边的排序用qsort还是自写排序、遇到权值相同的边怎么处理、结构体数组的大小怎么算边界……这篇文章会从原理到代码、从代码到踩坑完整过一遍。适合刚学完C语言基础、想进阶图论算法的学生也适合需要用C语言做课程设计或比赛刷题的人。2. 动手前的准备C语言环境和数据结构选型2.1 编译器和项目组织Kruskal算法本身没有平台相关性用任何标准C编译器都可以我在实际开发和调试中用的是**Visual Studio Code GCCMinGW-w64**的组合命令行编译命令很简单gcc -o kruskal kruskal.c -stdc11 -Wall -Wextra其中-Wall -Wextra一定要开因为Kruskal这种涉及数组下标和循环条件的代码编译器给到的警告往往能提前暴露越界或未初始化的问题。如果你用的是Visual Studio直接把源文件加入项目即可不需要额外配置什么第三方库整个实现全部基于C标准库。2.2 图的数据结构设计Kruskal算法处理的对象是边不是邻接矩阵也不是邻接表。这是它和Prim算法的一个明显差异Prim更偏向于稠密图通常用邻接矩阵或邻接表配合维护候选边集的思路而Kruskal天然适合**边集数组Edge List**这种简洁的数据结构直接用结构体数组把所有边存储起来。我常用的边结构体定义如下#define MAXV 100 // 最大顶点数 #define MAXE 5000 // 最大边数按无向图计算每条边存储一次 typedef struct { int u; // 边的起点 int v; // 边的终点 int w; // 边的权值 } Edge;这里要特别注意一个约定在Kruskal算法中图是有向还是无向体现在输入边的存储方式上。如果是无向图比如输入1 3 8表示顶点1和顶点3之间有一条权值为8的路径那么我们在边集数组里只存一条{1, 3, 8}就够了不需要另外存{3, 1, 8}。因为Kruskal的判断逻辑只关心两个端点是否连通不关心方向重复存储只会让排序和选边的效率白白降低。2.3 并查集是Kruskal的灵魂Kruskal算法的判断加入某条边是否会形成环这一步靠的就是并查集Union-Find Set。它的模型理解起来像一个班级里的小团体每个顶点一开始都只属于自己当选中一条边时就把两个端点所在的团体合并成一个如果某条边的两个端点已经属于同一个团体那加上这条边必然形成环必须跳过。并查集通常用两个数组实现int parent[MAXV]; // parent[i] 表示顶点i的父节点 int rank[MAXV]; // rank[i] 表示以i为根的树的高度近似值初始化时让parent[i] i表示每个顶点孤立成团。查找操作要带路径压缩合并操作要按**秩rank**合并目的是把并查集的查找均摊复杂度降到近O(1)让整个算法的时间瓶颈几乎只剩排序。3. Kruskal算法的完整代码实现从边排序到环路判断3.1 按权值给所有边排序既然贪心策略要求从小到大依次尝试那排序就是Kruskal的第一道工序。在C语言里最省事且最不容易写错的方式是使用标准库的qsort函数它需要我们自己写一个比较函数int cmpEdge(const void *a, const void *b) { Edge *ea (Edge *)a; Edge *eb (Edge *)b; return ea-w - eb-w; // 按权值升序排列 }然后这样调用qsort(edges, m, sizeof(Edge), cmpEdge);其中m是边数edges是我们的边数组。这里有个小坑值得提醒qsort的比较函数返回值是int如果你直接用return a-w - b-w;当权值最大值和最小值差距超过int的表数范围时会产生溢出不过实际题目里边的权值一般不超过10^5级别不会出问题但更稳妥的习惯是写成return (a-w b-w) - (a-w b-w);这个写法在任何情况下都绝对安全。如果你不想依赖标准库也可以自己写一个堆排序或归并排序实现方式也不难。但既然C标准库已经把高效的排序封装好了没必要重复造轮子除非是学习目的想看内部实现。3.2 并查集的查找与合并接下来是关键部分并查集基础函数。int find(int x) { // 查找x所属的集合根节点同时做路径压缩 if (parent[x] ! x) { parent[x] find(parent[x]); } return parent[x]; } void unionSet(int x, int y) { int rx find(x); int ry find(y); if (rx ry) return; // 按秩合并把矮树根接到高树根下防止并查集退化成链表 if (rank[rx] rank[ry]) { parent[rx] ry; } else if (rank[rx] rank[ry]) { parent[ry] rx; } else { parent[ry] rx; rank[rx]; } }find里的parent[x] find(parent[x]);就是路径压缩递归找到根之后顺手把路径上经过的所有节点的父节点直接指向根。这样下次再找这些节点的根就只需要一步。这里的递归深度在并查集中不会成为问题因为有了按秩合并树高最多是O(logN)量级加上路径压缩后基本是常数级别。3.3 选边主循环现在排序有了、并查集有了主循环的逻辑就非常顺了int kruskal(int n, int m, Edge *edges, Edge *result) { qsort(edges, m, sizeof(Edge), cmpEdge); for (int i 0; i n; i) { parent[i] i; rank[i] 0; } int cnt 0; // 已选边数 int weight 0; // 生成树总权值 int index 0; // result数组的下标 for (int i 0; i m cnt n - 1; i) { int ru find(edges[i].u); int rv find(edges[i].v); if (ru ! rv) { // 两端点不在同一个集合中这条边可以选 result[index] edges[i]; weight edges[i].w; unionSet(ru, rv); // 注意这里直接传根节点 cnt; } } if (cnt ! n - 1) { // 说明图不连通没有覆盖全部顶点 return -1; } return weight; }这里有一个很容易被忽视的细节unionSet(ru, rv)里我传的是已经find出来的根节点而不是原始端点。这是因为unionSet内部还会再调find一次但如果我们已经知道根了就可以省掉这次重复查找。反过来如果你直接在循环里写unionSet(edges[i].u, edges[i].v);逻辑也没错只是多了一次查找开销。代码风格上我倾向于循环里先取根、后合并读者看起来更清楚。3.4 为什么加入不会形成环的判断条件就是ru ! rv可能有人会问为什么只要两个顶点的根不同就一定能加这条边这里有个几何直觉如果u和v已经在同一个连通块里那么它们之间已经存在一条路径再加一条直接边就会在图中形成一个闭合回路而最小生成树的定义里要求无环反过来如果它们不在同一个连通块这条边就相当于是连接两座孤岛的一座桥加入它既能扩大连通范围又不会形成环。这个过程其实就是一种特殊的贪心策略。Kruskal算法的正确性呢有严格的数学证明主要依赖割属性和环路属性但理解了不连通则必为桥这一点已经足够你在代码中放心使用。4. 完整可运行的示例代码与测试用例4.1 整合一个可直接跑的程序为避免读者在拼接代码时出错我给出一个完整可直接编译运行的版本。这个程序会读取顶点数n和边数m然后逐行读取每条边的u v w最后输出最小生成树的总权值以及选中的每条边。#include stdio.h #include stdlib.h #define MAXV 100 #define MAXE 5000 typedef struct { int u, v, w; } Edge; Edge edges[MAXE]; Edge result[MAXE]; int parent[MAXV]; int rank[MAXV]; int cmpEdge(const void *a, const void *b) { Edge *ea (Edge *)a; Edge *eb (Edge *)b; return (ea-w eb-w) - (ea-w eb-w); } int find(int x) { if (parent[x] ! x) { parent[x] find(parent[x]); } return parent[x]; } void unionSet(int x, int y) { if (rank[x] rank[y]) { parent[x] y; } else if (rank[x] rank[y]) { parent[y] x; } else { parent[y] x; rank[x]; } } int kruskal(int n, int m, Edge *edges, Edge *result) { qsort(edges, m, sizeof(Edge), cmpEdge); for (int i 0; i n; i) { parent[i] i; rank[i] 0; } int cnt 0, weight 0, index 0; for (int i 0; i m cnt n - 1; i) { int ru find(edges[i].u); int rv find(edges[i].v); if (ru ! rv) { result[index] edges[i]; weight edges[i].w; unionSet(ru, rv); cnt; } } if (cnt ! n - 1) { return -1; } return weight; } int main() { int n, m; printf(请输入顶点数和边数用空格分隔: ); scanf(%d %d, n, m); printf(请输入 %d 条边每行格式: 起点 终点 权值\n, m); for (int i 0; i m; i) { scanf(%d %d %d, edges[i].u, edges[i].v, edges[i].w); } int total kruskal(n, m, edges, result); if (total -1) { printf(图不连通无法构成最小生成树\n); } else { printf(最小生成树总权值: %d\n, total); printf(选中的边:\n); for (int i 0; i n - 1; i) { printf((%d, %d, %d)\n, result[i].u, result[i].v, result[i].w); } } return 0; }4.2 用一个小图来验证我经常用下面这个经典例子来验证Kruskal是否正确。有5个顶点、7条边0 1 10 0 2 6 0 3 5 1 3 15 2 3 4 1 4 3 3 4 8手算一下按权值排序后依次尝试权值3的边(1,4)入权值4的边(2,3)入权值5的边(0,3)入此时已经连通了0、2、3、1、4五个节点中的4个但顶点0和1还不在同一集合……再看权值6的边(0,2)但0和2已经通过3连通了跳过权值8的边(3,4)同集合跳过权值10的边(0,1)此时0和1已经连通跳过权值15的边(1,3)同样跳过。最终选中3条边总权值34512这就是最小生成树的正确答案。在程序里运行的结果应该和手算完全一致。如果你得到不同的结果可以先检查scanf的输入格式是否对得上再看排序方向是不是写反了。我初学的时候就在这里栽过一次——比较函数写成了降序导致Kruskal直接变成了最大生成树输出结果完全不对。4.3 关于权值相同的边如何处理这是个很容易纠结的问题。如果排序后有多条边权值相等比如上面例子里的(1,4)和(2,3)如果权值一样那到底先选哪条答案是顺序不影响最终总权值的正确性。因为Kruskal算法只需要保证从小到大尝试相同权值的边无论先尝试哪一条最终得到的最小生成树总权值都一样只是选中的边集可能有多种合法组合而已。这个性质叫最小生成树不唯一但不影响总权值的最小性。5. 实测中的性能与边界问题不连通图、大边数、数组越界5.1 图不连通时怎么办程序里我用cnt ! n - 1来判断是否覆盖了所有顶点。如果循环结束后选边数不到N-1说明图中至少有一个顶点处在孤立的连通分量之外这时候就不存在包含全部顶点的生成树返回-1是一种常见的做法。实际比赛中有些题目会保证图连通但做通用工具时一定要加上这个判断否则后续逻辑可能因为result数组未填满而出错。5.2 多组输入与数组大小的选择很多练习题会要求多组测试数据直到EOF这时要注意在每组输入前重新初始化edges和parent数组。特别是edges数组不需要清空因为后面会重新用前m个位置但parent和rank必须在每组数据开始时重新初始化。我写过一版漏了rank数组的初始化结果在合并时出现随机行为排查了很久才发现是上一组数据残留导致的。5.3MAXE的上限到底怎么定如果用边集数组存无向图添加每条无向边时其实在逻辑上相当于双向可达但Kruskal只需要存一条。如果题目输入给的是每行两个顶点表示存在一条边那MAXE直接按题目给的边数上限来定即可。有一个常见的错误是输入一个完全图比如50个顶点理论上边数上限是50*49/21225有人却习惯性地把MAXE设成50*502500虽然不越界但浪费了内存。反过来如果顶点数是500完全图边数是124750MAXE设小了会导致数组越界这在C语言里可是轻则逻辑错误、重则段错误的隐患。一个稳妥的习惯是先看数据范围再定义数组边数不足时宁多勿少。6. Kruskal的实际应用与下一步提升方向6.1 应用场景并不只是铺网线最小生成树的应用绝对不限于题目和课本。举个现实的例子聚类分析里的单链接聚类法就等价于求最小生成树后砍掉权值较大的边图像分割里的某些算法也会先构造最小生成树网络设计中要在多个节点之间用最少电缆连接所有节点更是直接对应Kruskal或Prim。还有交通规划中要在多个城市之间修公路且总里程最小同样是个经典MST问题。如果你以后要参与一些物联网网关的选点设计比如在多个传感终端之间铺设数据总线Kruskal的思路照样可以直接套用——节点作为顶点两个节点之间的数据线成本作为边的权值最小生成树给出的就是总布线成本最低的方案。这也是为什么我建议学数据结构时不要只背代码而是把算法当成一个工具遇到实际问题时先抽象成图再选择合适算法。6.2 和Prim算法怎么选择在实现完Kruskal之后很多人会问那Prim呢两者的核心差别在策略上对比项Kruskal算法Prim算法核心思路按全局边的权值排序从小到大选边从一个顶点出发逐步扩展树外最小边数据结构边集数组 并查集邻接矩阵或邻接表 优先队列/数组时间复杂度O(E log E)主要开销在排序邻接矩阵O(V^2)二叉堆优化后O(E log V)适合场景稀疏图E接近V稠密图E接近V^2代码量较少逻辑直观稍多需要维护候选边集合简而言之边少用Kruskal点少用Prim。这只是一个参考实际上两种算法在小规模数据上都很快我自己在比赛中通常会看题目给出的点数范围来决定。如果V 500且是稠密图直接邻接矩阵Prim更省事如果V10000、E20000这种稀疏图Kruskal显然更合适。6.3 进阶堆优化的Kruskal如果想再进一步优化Kruskal可以把排序所有边改成把所有边放进最小堆每轮弹出堆顶。这样虽然时间复杂度没有本质变化但在某些需要在线加点或动态加边的场景下堆比全局排序更灵活。实现时可以先用qsort快速通过再用二叉堆优化来应对大数据量。不过如果是初学者我建议先把基础版本彻底吃透再研究堆优化否则容易一次接收太多概念反而混乱。7. 踩坑实录我在写Kruskal时经历过的几个迷之Bug这一节算是我自己的血泪总结希望能帮读者少走一些弯路。坑一qsort比较函数返回值的溢出问题。我第一次写直接用return a-w - b-w;测试数据小没事后来数据加强后惊奇地发现结果错了。排查半天发现是因为某两条边的权值一个极大一个极小差值溢出了导致比较函数返回了错误符号。从此我养成了习惯比较函数一律写成(a-w b-w) - (a-w b-w)或者显式分情况if-else绝不直接做减法。坑二并查集find函数没有路径压缩导致超时。初学并查集的时候我写的查找是int find(int x) { while (parent[x] ! x) x parent[x]; return x; }这个版本逻辑没错但没有路径压缩在大量查找操作下并查集树可能退化成长链复杂度逼近O(N)一次查找。当边数达到几十万级别时程序直接TLE。改成递归路径压缩后速度提升非常明显。事实上路径压缩和按秩合并是并查集性能的两个关键缺一不可。坑三数组下标从0开始还是从1开始没统一。我的边结构体里顶点编号习惯从0开始但有的题目输入从1开始这时候如果忘了统一转换很容易出现访问parent[0]和parent[n]混乱的情况。我的习惯是读入后立刻把u-1、v-1保证内部处理统一从0开始输出时再补回1。坑四无向图边重复存储。初学时我把无向图的边在数组里存了正反两条即{u,v,w}和{v,u,w}都存。结果Kruskal在选边时因为先选了其中一条另一条正反边就成了同集合内边被跳过逻辑虽然最终结果没错但浪费了一半的存储和排序开销数据量大时白白多耗时间。搞清楚了无向图的语义之后就没再犯过这个错。8. 我的个人调试技巧与最终建议最后再分享几个我平时调试Kruskal算法的小窍门。第一小数据手算验证是最有效的手段。不论是自己写测试样例还是看题目样例先手算一遍最小生成树再有意识地模拟程序执行能提前发现大量逻辑问题。第二中间结果打印尤其是每次选边前后的并查集状态。可以在unionSet之后加一行printf(select edge (%d,%d) weight%d\n, ...)观察选边过程是否符合预期。第三边界测试要带上最小数据一个顶点0条边、两个顶点1条边、三个顶点三条边但不成环的三角形等。很多同学只测常规数据结果n2这种最小边界直接越界或死循环。说实话Kruskal算法本身并不难难的是把并查集 排序这两个基本功扎实地用C语言表达出来。如果你能把上面的完整代码亲手敲一遍再改造成用malloc动态分配边数组的版本甚至加一个堆优化的版本你对C语言内存管理、结构体数组、函数指针、标准库排序的理解都会上一个台阶。这个练习过程带来的收获远不止会写一个算法那么简单。