用C语言完成克鲁斯卡尔算法完成最小生成树问题

克鲁斯卡尔算法是求最小生成树的经典算法之一，可以用来解决带权无向图的最小生成树问题，下面是用C语言实现克鲁斯卡尔算法求解最小生成树的代码：

#include <stdio.h>
#include <stdlib.h>

#define MAXVEX 100
#define MAXEDGE 10000

typedef struct {
    int u, v; //边的两个端点
    int w;    //边的权值
} Edge;

int cmp(const void *a, const void *b) {
    return (*(Edge *)a).w - (*(Edge *)b).w;
}

int parent[MAXVEX]; //并查集数组

//查找祖先
int find(int x) {
    int r = x;
    while (parent[r] != r) {
        r = parent[r];
    }
    //路径压缩
    int i = x, j;
    while (i != r) {
        j = parent[i];
        parent[i] = r;
        i = j;
    }
    return r;
}

//合并两个集合
void merge(int x, int y) {
    int fx = find(x), fy = find(y);
    if (fx != fy) {
        parent[fx] = fy;
    }
}

int main() {
    int n, m; //n个点，m条边
    Edge edge[MAXEDGE];
    scanf("%d%d", &n, &m);
    for (int i = 0; i < m; i++) {
        scanf("%d%d%d", &edge[i].u, &edge[i].v, &edge[i].w);
    }

    //按边权从小到大排序
    qsort(edge, m, sizeof(Edge), cmp);

    //初始化并查集
    for (int i = 1; i <= n; i++) {
        parent[i] = i;
    }

    int cnt = 0; //已选边数
    int sum = 0; //最小生成树的边权之和
    for (int i = 0; i < m; i++) {
        if (cnt == n - 1) {
            break;
        }
        int u = edge[i].u, v = edge[i].v, w = edge[i].w;
        if (find(u) != find(v)) {
            merge(u, v);
            sum += w;
            cnt++;
        }
    }

    printf("%d\n", sum);

    return 0;
}

代码中用了一个并查集来维护连通性，每次选取最小的边，如果该边的两个端点不在同一个集合中，则将它们合并，同时将该边的权值加入最小生成树的权值之和中。最后输出最小生成树的权值之和即可。