C语言实现最小生成树问题(Kruskal算法)
C语言实现最小生成树问题(Kruskal算法)
问题描述
某省调查乡村交通状况,得到的统计表中列出了任意两村庄间的距离。省政府'畅通工程'的目标是使全省任何两个村庄间都可以实现公路交通(但不一定有直接的公路相连,只要能间接通过公路可达即可),并要求铺设的公路总长度为最小。请计算最小的公路总长度。
输入
测试输入包含若干测试用例。每个测试用例的第1行给出村庄数目N ( < 100 );随后的N(N-1)/2行对应村庄间的距离,每行给出一对正整数,分别是两个村庄的编号,以及此两村庄间的距离。为简单起见,村庄从1到N编号。
当N为0时,输入结束,该用例不被处理。
输出
对每个测试用例,在1行里输出最小的公路总长度。
样例输入
3
1 2 1
1 3 2
2 3 4
4
1 2 1
1 3 4
1 4 1
2 3 3
2 4 2
3 4 5
0
样例输出
3
5
思路:Kruskal算法
- 将所有边按权值从小到大排序,每次选取一条权值最小的边,如果这条边的两个端点不在同一个连通块中,就将这两个连通块合并,并将这条边计入答案中。
- 直到选取了n-1条边,也就是所有点都在一个连通块中为止。
- 注意:此处的连通块指的是最小生成树的连通块,而不是原图的连通块。
**时间复杂度:**O(mlogm),其中m为边的数量。
代码:
#include <stdio.h>
#include <stdlib.h>
#define MAXN 100
struct Edge {
int u, v, w;
};
struct Edge edge[MAXN * MAXN]; // 存储所有边
int father[MAXN]; // 并查集数组
int n, m; // 顶点数和边数
int cmp(const void *a, const void *b) {
return ((struct Edge *)a)->w - ((struct Edge *)b)->w;
}
// 初始化并查集
void init() {
for (int i = 1; i <= n; i++) {
father[i] = i;
}
}
// 查找祖先
int find(int x) {
if (father[x] != x) {
father[x] = find(father[x]);
}
return father[x];
}
// 合并两个集合
void merge(int x, int y) {
father[find(x)] = find(y);
}
int kruskal() {
int ans = 0; // 最小生成树的总权值
int cnt = 0; // 已选边的数量
qsort(edge, m, sizeof(struct Edge), cmp);
init();
for (int i = 0; i < m; i++) {
int u = edge[i].u, v = edge[i].v, w = edge[i].w;
if (find(u) != find(v)) { // 两个端点不在同一个连通块中
merge(u, v); // 合并两个连通块
ans += w; // 将这条边计入答案
cnt++; // 已选边数量加1
if (cnt == n - 1) { // 已经选取了n-1条边,结束循环
break;
}
}
}
return ans;
}
int main() {
while (scanf('%d', &n) != EOF && n != 0) {
m = n * (n - 1) / 2; // 计算边的数量
for (int i = 0; i < m; i++) {
scanf('%d %d %d', &edge[i].u, &edge[i].v, &edge[i].w);
}
printf('%d
', kruskal());
}
return 0;
}
代码解释:
- 结构体
Edge: 用于存储边的信息,包括边的两个端点u和v,以及边的权值w。 - 数组
edge: 用于存储所有边的信息。 - 数组
father: 用于实现并查集,father[i]表示节点i的祖先节点。 - 变量
n和m: 分别表示顶点数和边数。 - 函数
cmp: 用于对边进行排序,按权值从小到大排序。 - 函数
init: 初始化并查集,将每个节点的祖先节点设为自身。 - 函数
find: 查找节点x的祖先节点,并进行路径压缩优化。 - 函数
merge: 合并两个集合,将其中一个集合的祖先节点指向另一个集合的祖先节点。 - 函数
kruskal: 实现Kruskal算法,返回最小生成树的总权值。 - 主函数
main: 输入数据,调用kruskal函数进行计算,并输出结果。
代码使用方法:
- 将代码保存为
.c文件,例如kruskal.c。 - 使用C语言编译器编译代码,例如
gcc kruskal.c -o kruskal。 - 运行可执行文件,例如
./kruskal,并输入测试数据。
总结:
本文介绍了如何使用C语言实现最小生成树问题,并详细讲解了Kruskal算法的思路、时间复杂度和代码实现。通过这个例子,可以更好地理解最小生成树问题的求解方法,以及并查集数据结构在算法中的应用。
原文地址: https://www.cveoy.top/t/topic/n8hV 著作权归作者所有。请勿转载和采集!