利用克鲁斯卡尔算法求最小生成树c语言

以下是利用克鲁斯卡尔算法求最小生成树的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 edge[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]);
}

// 克鲁斯卡尔算法求最小生成树
void kruskal(int n, int m) {
    int i, j, cnt = 0, ans = 0;
    for (i = 1; i <= n; i++) {
        parent[i] = i;
    }
    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;
        int x = find(u), y = find(v);
        if (x != y) { // 如果不在同一个集合中，说明不会形成环
            parent[x] = y; // 合并集合
            ans += w; // 累加权值
            cnt++; // 计数器加1
            if (cnt == n - 1) { // 边数达到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", &edge[i].u, &edge[i].v, &edge[i].w);
    }
    kruskal(n, m);
    return 0;
}