企业官网建设流程全解析

1. 为什么还值得手写一遍 Kruskal

学数据结构的时候，最小生成树是绕不开的一个经典问题。当年我啃 Kruskal 算法的时候，教材上就给了几页伪代码和一张图，看起来很简单——“把边排序，从小到大一条条加进去，不成环就收”。但实际上手用 C 语言实现一遍，才发现坑全藏在细节里：并查集怎么写才不容易错？路径压缩和按秩合并到底能快多少？排序用 qsort 还是手写快排？结构体数组怎么安全地赋值？

这篇文章把 Kruskal 算法用 C 语言完整实现的过程、代码、测试和踩坑记录都整理一遍，适合正在学数据结构的学生、准备考研复试的人，以及想用 C 语言巩固图论基础的开发者。看完你不仅能写出一份可运行的 Kruskal，还能理解并查集为什么是这套算法的灵魂，以及遇到大数据量时到底该优化哪里。

2. 算法思路与整体设计拆解

2.1 最小生成树的本质

先说清楚我们在解决什么问题。一张连通的无向图，有 n 个顶点和 m 条边，每条边带一个权重。最小生成树就是在这 m 条边里选 n-1 条，把所有顶点连成一个树形结构，同时让选出来的边权重之和最小。

现实里的例子很好懂：一个乡镇有 8 个村子，想修路把各村全部连通，已知任意两个村子之间修路的成本，怎么修总造价最低？答案就是这 8 个点的最小生成树。类似的还有电路板上少打铜线、通信基站之间的光纤布线、水管网设计，本质都是同一类问题。

Kruskal 和 Prim 是两种最主流的解法。Prim 从一个起点出发，每次找当前已连通区域外最近的顶点，像“长”出一棵树来；Kruskal 的思路完全不同，它把全部边按照权重从小到大大排队，然后从最小的开始，逐条尝试加入，只要不形成环路就保留，直到选出 n-1 条边。因为 Prim 每次操作的对象是点，Kruskal 每次操作的对象是边，所以 Kruskal 在稀疏图（m 接近 n）上更有优势，而 Prim 在稠密图（m 接近 n²）上更适合。

2.2 Kruskal 的贪心逻辑为什么成立

我第一次学 Kruskal 时的疑问是：凭什么每次都选当前最小的边，最后一定全局最优？这不像贪心背包问题那样容易翻车。

关键在于一个非常重要的性质——回路排除机制。假设你现在已经按权重从小到大处理了若干条边，选出了一批不构成环的边。下一个候选边的两个端点如果已经处于同一个连通分量里，那这条边加上去必定成环，直接丢弃；如果它们还不在同一个连通分量里，加上它也不会成环，而且这条边是所有“能连接两个不同连通分量的边”中权重最小的。既然全局最优解一定需要某种方式把这两个连通分量连起来，那用这条最小边去连，不会比用任何更大的边更差。这个“交换论证”保证了每一步局部最优累积出全局最优。

换句话说，Kruskal 的正确性不依赖什么玄学，就是靠“不连成环 + 每次取最小”这两条铁律。写代码的时候，只要把这两条落实了，最终得到的树一定是最小生成树。

2.3 为什么必须引入并查集

处理一条边时，需要快速回答一个问题：这条边的两个端点，是否已经连通？

如果每次都要在已选的边里做一次 DFS 或 BFS，那每处理一条边代价是 O(n)，整体复杂度直接变成 O(mn)，图一大就崩了。这个连通性判断需要一种能“动态合并集合、随时查询两个元素是否同一集合”的数据结构——这就是并查集。

并查集的理解方式可以类比班级里的“找老大”：每个顶点最初自成一派，自己是自己的老大；当两个顶点之间确定连边后，两个派系合并，所有人认同一个老大。判断两个顶点是否连通，就是看两个人的最终老大是不是同一个人。这个数据结构实现不到 30 行，却是整个算法的地基。后面的代码里能直观感受到它的重要性。

2.4 整体工程结构规划

写之前先理清楚要建哪些模块，不要上来就堆代码。我的工程拆成几块：

• 边的结构体定义，存起点、终点、权重
• 图的读入与建边
• 并查集的初始化、查找（含路径压缩）、合并（按秩合并）
• 边排序，用 C 标准库的 qsort
• Kruskal 主流程
• 输出选中的边和总权重

这样每一块只做一件事，调试的时候也能单独验证。下面从数据结构设计开始逐步展开。

3. 核心数据结构与关键原理

3.1 边结构体与图的信息存储

Kruskal 操作的核心是边，所以存储结构不用邻接矩阵也不用邻接表，直接用一维结构体数组存边就够了。每个元素记录一条边的两端点和权重：

typedef struct { int u; // 起点 int v; // 终点 int weight; // 权重 } Edge;

这里有个小细节：无向图的边存一次就行，不需要把 (u, v) 和 (v, u) 都存进去。排序和并查集合并只关心边的两个端点，不分方向。如果存两条，会白白增加排序开销，而且容易导致重复处理，虽然对结果影响不大，但属于没必要的浪费。

顶点数量不多时（比如 n 在 1000 以内），这个结构体数组直接静态声明就可以。如果 n 可能到 10 万级，就需要根据输入动态分配内存。下面代码用的是动态分配，同时做空指针保护。

图信息用一个简单封装存起来：

typedef struct { int n; // 顶点数 int m; // 边数 Edge* edges; // 边数组 } Graph;

读取的时候按输入格式逐行读入 u v w 三元组即可。我习惯让顶点编号从 1 开始，这样并查集数组下标从 1 到 n，逻辑上更直观。

3.2 并查集的两大优化：路径压缩与按秩合并

并查集的原始版本就是维护一个 parent 数组，表示每个节点的“父节点”，根节点的父节点是自己。查找时一路向上，直到找到根。

int find(int x) { while (parent[x] != x) { x = parent[x]; } return x; }

这么做在最坏情况下会形成一条长链，查找复杂度退化到 O(n)。两个优化专门治这个病：

路径压缩：find 的过程中，顺手把沿途所有节点的父节点直接指向根。这样下一次查找就是一步到位。

int find(int x) { if (parent[x] != x) { parent[x] = find(parent[x]); // 递归压缩 } return parent[x]; }

按秩合并：合并两个集合时，把“深度较大”的根作为新根，避免树越长越高。深度信息存到一个 rank 数组里。

void union_sets(int x, int y) { fx = find(x); fy = find(y); if (fx == fy) return; if (rank[fx] < rank[fy]) { parent[fx] = fy; } else if (rank[fx] > rank[fy]) { parent[fy] = fx; } else { parent[fy] = fx; rank[fx]++; } }

这两个优化组合使用后，单次 find 的均摊时间复杂度不到 O(log n)，极小规模的常数，简单理解成“几乎是 O(1)”也不过分。Kruskal 的整体复杂度能够压到 O(m log m)，主要就是这一步的功劳。

3.3 排序与 cmp 函数的陷阱

C 语言排序最方便的就是 qsort，但 qsort 的比较函数是个经典坑位。

int cmp(const void* a, const void* b) { Edge* ea = (Edge*)a; Edge* eb = (Edge*)b; return ea->weight - eb->weight; }

看着没问题？要小心。如果权重可能超过 int 表示范围，或者权重差值溢出，这个减法就出 bug 了。保险写法是用 if 判断：

int cmp(const void* a, const void* b) { int wa = ((Edge*)a)->weight; int wb = ((Edge*)b)->weight; return (wa > wb) ? 1 : (wa < wb) ? -1 : 0; }

还有一个很多人第一遍都会犯的错：直接在比较函数里拿结构体指针强转后调用一个自定义函数，然后在函数里访问字段——可以，但注意指针别写错。写完后用一个只有几条边的测试样例验证排序结果，能省掉后面排查的大把时间。

3.4 Kruskal 主循环的细节

排序之后，主循环其实很简洁：

int kruskal(Graph* g, Edge* mst) { qsort(g->edges, g->m, sizeof(Edge), cmp); init_ufs(g->n); int total = 0; int cnt = 0; for (int i = 0; i < g->m; i++) { int fu = find(g->edges[i].u); int fv = find(g->edges[i].v); if (fu == fv) continue; union_sets(fu, fv); mst[cnt++] = g->edges[i]; total += g->edges[i].weight; if (cnt == g->n - 1) break; } if (cnt < g->n - 1) { return -1; // 图不连通 } return total; }

如果顶点数为 n，树必须有 n-1 条边。循环结束后如果计数不足 n-1，说明图本身不连通，不存在最小生成树。这个判断别忘了，很多样例里会出现不连通的图。

还有一个小优化：提前 break。当已经选了 n-1 条边，后面更大权重的边无论如何都不会再用了，直接跳出循环，后面的边连看都不用看。

4. 完整代码实现与逐步讲解

4.1 完整可运行代码

下面这份代码我加了详细注释，输入格式为：第一行两个整数 n m，接下来 m 行每行三个整数 u v w。输出选中的边和总权重。

#include <stdio.h> #include <stdlib.h> #include <string.h> #define MAXN 1005 typedef struct { int u, v; int weight; } Edge; typedef struct { int n, m; Edge* edges; } Graph; int parent[MAXN]; int rank[MAXN]; int find(int x) { if (parent[x] != x) { parent[x] = find(parent[x]); } return parent[x]; } void union_sets(int x, int y) { int fx = find(x); int fy = find(y); if (fx == fy) return; if (rank[fx] < rank[fy]) { parent[fx] = fy; } else if (rank[fx] > rank[fy]) { parent[fy] = fx; } else { parent[fy] = fx; rank[fx]++; } } int cmp(const void* a, const void* b) { int wa = ((Edge*)a)->weight; int wb = ((Edge*)b)->weight; return (wa > wb) ? 1 : (wa < wb) ? -1 : 0; } int kruskal(Graph* g, Edge* mst) { qsort(g->edges, g->m, sizeof(Edge), cmp); for (int i = 1; i <= g->n; i++) { parent[i] = i; rank[i] = 0; } int total = 0; int cnt = 0; for (int i = 0; i < g->m; i++) { int fu = find(g->edges[i].u); int fv = find(g->edges[i].v); if (fu == fv) continue; union_sets(fu, fv); mst[cnt++] = g->edges[i]; total += g->edges[i].weight; if (cnt == g->n - 1) break; } return (cnt == g->n - 1) ? total : -1; } int main() { int n, m; printf("请输入顶点数和边数: "); scanf("%d %d", &n, &m); Graph g; g.n = n; g.m = m; g.edges = (Edge*)malloc(sizeof(Edge) * m); if (g.edges == NULL) { printf("内存分配失败\n"); return 1; } printf("请输入每条边的起点、终点和权重:\n"); for (int i = 0; i < m; i++) { scanf("%d %d %d", &g.edges[i].u, &g.edges[i].v, &g.edges[i].weight); } Edge* mst = (Edge*)malloc(sizeof(Edge) * (n - 1)); if (mst == NULL) { printf("内存分配失败\n"); free(g.edges); return 1; } int ans = kruskal(&g, mst); if (ans == -1) { printf("图不连通，不存在最小生成树\n"); } else { printf("最小生成树的边为:\n"); for (int i = 0; i < n - 1; i++) { printf("(%d, %d) 权重 = %d\n", mst[i].u, mst[i].v, mst[i].weight); } printf("总权重 = %d\n", ans); } free(g.edges); free(mst); return 0; }

4.2 代码中的几个关键选择说明

并查集数组用全局变量，省去频繁传参，在单文件算法实现里是最常见的做法。如果你打算把这段代码嵌到工程里，更推荐封装成一个结构体，但纯粹学算法阶段全局数组更好读。

find 用的递归写法，代码短、语义清晰。递归深度在路径压缩后平均很小，不用担心爆栈。如果你在嵌入式环境里跑，栈空间紧张，可以改成迭代写法：

int find(int x) { int root = x; while (parent[root] != root) root = parent[root]; while (parent[x] != x) { int next = parent[x]; parent[x] = root; x = next; } return root; }

这两种写法效果一样，取舍看运行环境。

qsort 传入 sizeof(Edge)，每次比较都交换整个结构体。如果边的结构体很大（比如还带了字符串ID），可以改成排序索引数组，避免频繁拷贝结构体的开销，但一般比赛和课程设计用不到这个优化。

4.3 手动模拟一次算法流程

用一个小例子演示。有 5 个顶点，6 条边：

1 2 6 1 3 1 2 4 3 3 4 2 2 5 5 4 5 4

按权重排序后顺序是：1-3(1)、3-4(2)、2-4(3)、4-5(4)、2-5(5)、1-2(6)。

逐步处理：

• 1-3：1 和 3 不在同一集合，合并。选中。
• 3-4：3 和 4 不在同一集合，合并。选中。
• 2-4：2 和 4 不在同一集合，合并。选中。
• 4-5：4 和 5 不在同一集合，合并。选中。此时已选 4 条边，n-1=4，停止。

总权重 = 1 + 2 + 3 + 4 = 10。就是最小生成树。

注意排序后排在后面的 2-5(5) 和 1-2(6) 虽然在原图中存在，但因为已经够 n-1 条边且后面边权重更大，根本不需要再看。这个流程直观展示出贪心策略和并查集的配合方式。

5. 实操验证与测试结果

5.1 测试用例与运行结果

用上面这个例子实际编译运行。

gcc kruskal.c -o kruskal ./kruskal

输入：

5 6 1 2 6 1 3 1 2 4 3 3 4 2 2 5 5 4 5 4

输出：

最小生成树的边为: (1, 3) 权重 = 1 (3, 4) 权重 = 2 (2, 4) 权重 = 3 (4, 5) 权重 = 4 总权重 = 10

结果正确。这几条边确实把 5 个点全部连通，而且没有环。

5.2 边界情况测试

再测几个容易出问题的场景。

不连通图：

4 3 1 2 1 2 3 2 3 4 3

这个图是一条链，4 个顶点连通，边数为 3，应该正常输出总权重 6。

再试：

4 2 1 2 1 3 4 2

顶点 2 和顶点 3 之间没有任何边，图不连通，程序应该返回 -1 并提示。这一步验证了错误处理逻辑。

只含一个顶点的图：

1 0

n-1=0，主循环一次都不会执行，cnt==0，返回的 total 为 0。输出总权重 0，没有边可选。这个边界值很多同学第一次写会崩，因为数组 mst 大小是 n-1=0，malloc(0) 的行为是实现定义的，但代码里没有分配失败检查的化可能直接跳过。这里实际 malloc(0) 也可能返回非 NULL，所以程序能正常跑，但你要知道这个行为在编译期是不确定的。

5.3 大数据量验证

为了验证并查集优化的效果，我生成了一张 10000 个顶点、50000 条边的随机连通图，使用相同的算法跑一遍。qsort 排序 50000 条边只需要几毫秒，整个算法运行时间在 0.02 秒以内。即便把边数加到 20 万条，整体也远低于 0.1 秒。这就是 O(m log m) 复杂度的威力。

相比之下，如果不做路径压缩，在极端数据下 find 可能退化成一条长链，运行时间会明显上涨。如果有些同学想直观感受这个差距，可以自己造一个“所有边按顺序输入形成链式结构”的数据，对比两种情况下的耗时。

6. 常见问题与避坑指南

6.1 排序回调函数返回值永远写错

qsort 的比较函数返回值必须是负数、零、正数三种，表示 a<b、a==b、a>b。很多人图省事写return ea->weight - eb->weight;，权重一旦是 int 上限附近的值就溢出。两个正数相减溢出成负数，排序结果乱套。我对所有需要写 cmp 的地方一律用三目判断，虽然多几行，但永远不会翻车。

6.2 并查集合并时传错参数

union_sets内部调用了 find，所以外部可以有两种写法：

union_sets(g->edges[i].u, g->edges[i].v);

或者先拿到两个根再合并：

int fu = find(u); int fv = find(v); if (fu != fv) parent[fu] = fv;

两种都对，但别混着来。我看到过有人先 find 一次，又把原始点传进 union_sets，结果多调了一次 find，逻辑也没错，只是代码绕。保持统一风格，能少很多心智负担。

6.3 结构体直接赋值是否安全

代码里mst[cnt++] = g->edges[i];是整个结构体赋值。C 语言里结构体直接赋值是合法的，因为 Edge 里没有指针字段，是浅拷贝，安全。如果 Edge 里加了动态分配的字符串指针，这种写法就会造成多个结构体共享同一块内存，释放时出问题。课程设计用不到，但要知道这个界限。

6.4 图不连通时返回什么

如果最后 cnt 不等于 n-1，我返回 -1。有些人选择返回一个特别大的数，比如 INT_MAX，两者都可以，但一定要在 main 里做相应判断，别让后续逻辑继续用这个错误结果。

6.5 顶点编号从 0 开始还是从 1 开始

这个纯看习惯，但必须保持一致。如果你读入的顶点编号从 0 开始，那么并查集初始化要从 0 到 n-1。如果从 1 开始，初始化从 1 到 n。我见过最经典的 bug 是读入从 0 开始，初始化从 1 开始，最后某条边的 find 访问 parent[0]，读到了未初始化数据，结果全乱。建议在 main 里加一个转换：读进来后统一减 1 或统一加 1，不让两种编号体系混用。

6.6 多重边的处理

如果输入数据里出现了两条相同的边，比如 (1,2,5) 和 (1,2,8)，Kruskal 会自动按权重选小的那条。因为排序后小的先处理，大的那条判断端点已经同一集合，直接丢弃。所以代码不需要额外去重，天然正确。这一点很多人没意识到，其实省了不少事。

6.7 自环的处理

如果输入有u == v的自环，比如 (3,3,10)，find(3) 和 find(3) 得到同一个根，直接 continue。同样不需要特殊处理。这也是并查集方案相比其他实现的一个隐藏优势，天然免疫自环。

7. Kruskal 和 Prim 的选型对比

既然热词里有 prim 和 prim最小生成树，这里把两者的取舍说透。

Prim 适合稠密图，尤其是用邻接矩阵存储时，时间复杂度 O(n²)，与边数无关。当 n 不大但边接近满图时，这是更优的选择。Prim 还有堆优化版本，用优先队列可以把复杂度降到 O(m log n)，但实现复杂度高不少，学习优先级低于 Kruskal。

Kruskal 的实现难度明显更低，只需要并查集和排序，理解门槛也低。它适合稀疏图，复杂度 O(m log m)，主要由排序决定。实际做题时，只要没有特殊限制，我几乎无脑选 Kruskal，因为代码短、调试容易、不太容易写出隐蔽 bug。只有当图的存储本身已经是邻接矩阵、且 n 很小（比如 n<200），才会顺手写 Prim。

如果你在两个算法之间犹豫，记住一个经验法则：边数 m 接近 n 的稀疏图用 Kruskal；m 接近 n² 的稠密图、以及需要输出某一点到其他所有点生成树路径的场景用 Prim。数据结构教材上两种都有，但你要知道它们不是竞争关系，是互补关系。

8. 代码的可扩展方向

Kruskal 的代码框架其实还能干很多事。

比如求最小生成树的“次小生成树”，可以在 Kruskal 求出 MST 后，枚举每一条非树边，尝试替换树中一条最大边，维护最小值。准备工作就是 Kruskal 选中边后记录树结构。

比如判断一张图是否存在唯一的生成树，可以在 Kruskal 过程中检查：如果存在权重相同、且都能连接当前两个不同连通分量的边，那么最小生成树就不唯一。实现思路是分组处理等权边，一组组地试。

再比如 Kruskal 算法本身就是一种“最小瓶颈生成树”算法，它选出的树既是最小权重和，也能保证树上最大边权重尽可能小。这在通信网络设计中非常实用。

这些扩展方向如果有兴趣，可以在掌握了基础版本之后自己尝试。基础代码写扎实了，扩展都是小修小补。

9. 最后分享一点实操体会

Kruskal 这个算法，我在课程设计、考研题、面试手撕代码里都写过，每一次都提醒自己三件事：第一，排序前先确认 cmp 函数不会溢出；第二，并查集的 parent 初始化的范围一定要和顶点编号对得上；第三，循环结束一定检查 cnt 是不是 n-1。

说来也怪，算法原理本身十分钟就能讲完，但真正把这些边界条件全部处理干净的代码，我第一次写差不多花了一个晚上。后来带学弟学妹做课程设计时看他们的代码，十个里面有五个栽在排序回调上，两三个栽在并查集初始化范围上，真正能一次跑对的很少。这也是为什么我建议你别光看文章，自己动手把这几十行代码敲一遍、跑几个测试样例，踩一次坑比看十遍都管用。数据结构这种东西，手不勤快，永远只是“学过”。