掌握Kruskal算法的实现方法c语言
时间: 2023-12-18 13:09:08 浏览: 30
Kruskal算法是一种用于解决最小生成树问题的贪心算法。这里是Kruskal算法的C语言实现方法:
```
#include <stdio.h>
#include <stdlib.h>
#define MAXV 1000
#define MAXE 10000
typedef struct {
int u, v, w;
} Edge;
Edge edges[MAXE];
int parent[MAXV], rank[MAXV];
int cmp(const void *a, const void *b) {
return ((Edge*)a)->w - ((Edge*)b)->w;
}
int find(int x) {
if (parent[x] != x)
parent[x] = find(parent[x]);
return parent[x];
}
void merge(int x, int y) {
x = find(x), y = find(y);
if (rank[x] > rank[y])
parent[y] = x;
else {
parent[x] = y;
if (rank[x] == rank[y])
rank[y]++;
}
}
int main() {
int n, m, i, j, k;
scanf("%d %d", &n, &m);
for (i = 0; i < m; i++)
scanf("%d %d %d", &edges[i].u, &edges[i].v, &edges[i].w);
qsort(edges, m, sizeof(Edge), cmp);
for (i = 1; i <= n; i++)
parent[i] = i, rank[i] = 0;
int ans = 0;
for (i = 0; i < m; i++) {
if (find(edges[i].u) != find(edges[i].v)) {
merge(edges[i].u, edges[i].v);
ans += edges[i].w;
}
}
printf("%d\n", ans);
return 0;
}
```
在这个程序中,我们首先定义了一个结构体Edge,它包含了一条边的起点、终点和边权。然后我们定义了两个数组parent和rank,它们分别用于存储每个点的父节点和秩。
在输入完边后,我们使用qsort函数对边按照边权从小到大进行排序。排序后,我们初始化parent数组和rank数组。初始时,每个点的父节点都是它自己,秩都为0。
接下来,我们遍历每一条边,如果这条边的起点和终点不在同一集合中,就将它们合并,更新ans的值。这里使用了并查集来维护集合,可以快速地判断两个点是否在同一集合中。
最后输出ans的值,即为最小生成树的权值。