C语言最小生成树代码
时间: 2023-11-29 07:44:42 浏览: 85
最 小生成树.zip
以下是C语言实现Kruskal算法求解最小生成树的代码:
```c
#include <stdio.h>
#include <stdlib.h>
#define MAX_EDGE_NUM 100 // 最大边数
#define MAX_VERTEX_NUM 100 // 最大顶点数
typedef struct {
int u; // 边的起点
int v; // 边的终点
int w; // 边的权值
} Edge;
Edge edges[MAX_EDGE_NUM]; // 存储边的数组
int parent[MAX_VERTEX_NUM]; // 并查集数组
// 比较函数,用于qsort排序
int cmp(const void *a, const void *b) {
return ((Edge *)a)->w - ((Edge *)b)->w;
}
// 并查集查找函数
int find(int x) {
if (parent[x] == x) {
return x;
}
return parent[x] = find(parent[x]);
}
// Kruskal算法求解最小生成树
void kruskal(int n, int m) {
int i, j, cnt = 0, ans = 0;
for (i = 1; i <= n; i++) {
parent[i] = i;
}
qsort(edges, m, sizeof(Edge), cmp);
for (i = 0; i < m; i++) {
int u = edges[i].u, v = edges[i].v, w = edges[i].w;
int pu = find(u), pv = find(v);
if (pu != pv) {
parent[pu] = pv;
ans += w;
cnt++;
if (cnt == 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;
}
```
阅读全文