克鲁斯卡尔算法c语言实现
时间: 2023-11-19 07:07:23 浏览: 94
以下是克鲁斯卡尔算法的C语言实现:
```c
#include <stdio.h>
#include <stdlib.h>
#define MAX 1000
typedef struct {
int u, v, w;
} Edge;
Edge edge[MAX];
int parent[MAX];
int rank[MAX];
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) {
int px = find(x), py = find(y);
if (rank[px] > rank[py]) {
parent[py] = px;
} else {
parent[px] = py;
if (rank[px] == rank[py]) {
rank[py]++;
}
}
}
void kruskal(int n, int m) {
int i, cnt = 0;
for (i = 1; i <= n; i++) {
parent[i] = i;
rank[i] = 0;
}
qsort(edge, m, sizeof(Edge), cmp);
for (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);
printf("%d %d %d\n", u, v, w);
cnt++;
if (cnt == n - 1) {
break;
}
}
}
}
int main() {
int n, m, i;
scanf("%d%d", &n, &m);
for (i = 0; i < m; i++) {
scanf("%d%d%d", &edge[i].u, &edge[i].v, &edge[i].w);
}
kruskal(n, m);
return 0;
}
```
阅读全文