c语言写kruskal算法代码
时间: 2023-05-11 11:04:40 浏览: 55
以下是 C 语言写 Kruskal 算法的代码:
```
#include <stdio.h>
#include <stdlib.h>
#define MAX_VERTICES 100
#define MAX_EDGES 10000
typedef struct {
int u, v, w;
} Edge;
int parent[MAX_VERTICES];
int find(int x) {
if (parent[x] == x) {
return x;
} else {
return parent[x] = find(parent[x]);
}
}
void union_set(int x, int y) {
parent[find(x)] = find(y);
}
int cmp(const void *a, const void *b) {
return ((Edge *)a)->w - ((Edge *)b)->w;
}
int main() {
int n, m;
Edge edges[MAX_EDGES];
scanf("%d%d", &n, &m);
for (int i = 0; i < m; i++) {
scanf("%d%d%d", &edges[i].u, &edges[i].v, &edges[i].w);
}
for (int i = 1; i <= n; i++) {
parent[i] = i;
}
qsort(edges, m, sizeof(Edge), cmp);
int ans = 0;
for (int i = 0; i < m; i++) {
int u = edges[i].u, v = edges[i].v, w = edges[i].w;
if (find(u) != find(v)) {
union_set(u, v);
ans += w;
}
}
printf("%d\n", ans);
return 0;
}
```
这是一个简单的 Kruskal 算法实现,输入格式为:
```
n m
u1 v1 w1
u2 v2 w2
...
um vm wm
```
其中 n 表示节点数,m 表示边数,后面 m 行表示每条边的起点、终点和权值。输出最小生成树的权值。