kruskal算法c语言
时间: 2023-08-24 18:35:12 浏览: 72
Kruskal算法是一种最小生成树算法,其基本思想是:将所有边按照权值从小到大排序,然后依次加入到生成树中,同时需要保证加入的边不会构成环,直到生成树中有n-1条边为止。
以下是使用C语言实现Kruskal算法的例子:
```c
#include <stdio.h>
#include <stdlib.h>
#define MAX_VERTICES 1000 // 最大顶点数
#define MAX_EDGES 1000000 // 最大边数
typedef struct {
int u, v; // 边的两个端点
int w; // 边的权值
} Edge;
Edge edges[MAX_EDGES]; // 所有边的数组
int n, m; // 顶点数和边数
int parent[MAX_VERTICES]; // 并查集数组
// 并查集查找祖先
int find(int x) {
if (parent[x] == x) {
return x;
}
return parent[x] = find(parent[x]);
}
// 并查集合并
void merge(int x, int y) {
parent[find(x)] = find(y);
}
// 边的比较函数
int cmp(const void* a, const void* b) {
return ((Edge*)a)->w - ((Edge*)b)->w;
}
// Kruskal算法求最小生成树
void kruskal() {
int i, j, cnt = 0;
long long ans = 0; // 最小生成树的权值
for (i = 1; i <= n; i++) {
parent[i] = i;
}
qsort(edges, m, sizeof(Edge), cmp);
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;
cnt++;
if (cnt == n - 1) {
break;
}
}
}
printf("%lld\n", ans);
}
int main() {
int i;
scanf("%d%d", &n, &m);
for (i = 0; i < m; i++) {
scanf("%d%d%d", &edges[i].u, &edges[i].v, &edges[i].w);
}
kruskal();
return 0;
}
```
该程序首先读入顶点数n和边数m,然后读入m条边的信息,存储在edges数组中。在kruskal函数中,将边按照权值从小到大排序,然后依次加入到生成树中,同时需要保证加入的边不会构成环。
程序使用并查集来判断两个顶点是否在同一连通块中,避免了使用DFS或BFS遍历整个图的复杂度。最终输出最小生成树的权值。