kruskal算法c
时间: 2023-12-12 13:34:09 浏览: 22
以下是Kruskal算法的C语言实现,其中包括并查集的实现:
```c
#include <stdio.h>
#include <stdlib.h>
#define MAX_EDGE_NUM 1000 // 最大边数
#define MAX_VERTEX_NUM 100 // 最大顶点数
typedef struct Edge {
int u, v, w; // 边的起点、终点、权值
} Edge;
Edge edges[MAX_EDGE_NUM]; // 存储所有边的数组
int father[MAX_VERTEX_NUM]; // 并查集数组,用于判断两个顶点是否在同一个连通块中
// 并查集查询函数,查询根结点+路径压缩
int findFather(int x) {
if (father[x] != x) {
father[x] = findFather(father[x]);
}
return father[x];
}
// Kruskal算法实现函数
void kruskal(int n, int m) {
int i, j, cnt = 0, ans = 0;
for (i = 1; i <= n; i++) {
father[i] = i; // 初始化并查集数组
}
for (i = 0; i < m; i++) {
int u = edges[i].u, v = edges[i].v, w = edges[i].w;
int faU = findFather(u), faV = findFather(v);
if (faU != faV) { // 如果两个顶点不在同一个连通块中
father[faU] = faV; // 合并两个连通块
ans += w; // 累加边权值
cnt++; // 计数器加1
if (cnt == n - 1) { // 如果已经找到n-1条边,即为最小生成树
break;
}
}
}
printf("最小生成树的权值为:%d\n", ans);
}
int main() {
int n, m, i;
printf("请输入顶点数和边数:\n");
scanf("%d%d", &n, &m);
printf("请输入每条边的起点、终点、权值:\n");
for (i = 0; i < m; i++) {
scanf("%d%d%d", &edges[i].u, &edges[i].v, &edges[i].w);
}
kruskal(n, m);
return 0;
}
```