请用c语言编程实现Kruskal算法
时间: 2023-12-18 18:18:00 浏览: 36
Kruskal算法是求解最小生成树的一种贪心算法,具体步骤如下:
1. 将所有边按照权值从小到大排序;
2. 从小到大遍历每条边,如果这条边的两个端点不在同一个连通块中,则将其加入最小生成树中;
3. 重复步骤2,直到最小生成树中有n-1条边,其中n为节点数。
下面是用C语言实现Kruskal算法的代码:
```
#include <stdio.h>
#include <stdlib.h>
#define MAXN 1000
#define MAXM 100000
typedef struct {
int u, v, w;
} Edge;
int n, m;
Edge edges[MAXM+5];
int father[MAXN+5];
int cmp(const void *a, const void *b) {
return ((Edge *)a)->w - ((Edge *)b)->w;
}
int find(int x) {
if (father[x] == x) return x;
return father[x] = find(father[x]);
}
void merge(int x, int y) {
father[find(x)] = find(y);
}
int kruskal() {
int ans = 0, cnt = 0;
for (int i = 1; i <= n; i++) father[i] = i;
qsort(edges+1, m, sizeof(Edge), cmp);
for (int i = 1; i <= m; i++) {
if (find(edges[i].u) != find(edges[i].v)) {
merge(edges[i].u, edges[i].v);
ans += edges[i].w;
cnt++;
if (cnt == n-1) break;
}
}
return ans;
}
int main() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= m; i++) {
scanf("%d%d%d", &edges[i].u, &edges[i].v, &edges[i].w);
}
printf("%d\n", kruskal());
return 0;
}
```
其中,cmp函数用于按照边权从小到大排序,find函数和merge函数用于维护并查集,kruskal函数用于执行Kruskal算法,最后打印出最小生成树的权值。