数据结构 C语言设计一个c语言程序实现采用克鲁斯卡尔算法求最小生成树

好的，下面是一个简单的C语言程序实现克鲁斯卡尔算法求解最小生成树。

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

#define MAX_EDGE_NUM 100
#define MAX_VERTEX_NUM 50

typedef struct {
    int u;  // 边的起点
    int v;  // 边的终点
    int w;  // 边的权重
} Edge;

int parent[MAX_VERTEX_NUM];  // 并查集父节点

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

int find(int x) {
    if (parent[x] != x) {
        parent[x] = find(parent[x]);
    }
    return parent[x];
}

void union_set(int x, int y) {
    int px = find(x);
    int py = find(y);
    if (px != py) {
        parent[px] = py;
    }
}

void kruskal(Edge edges[], int n, int m) {
    int i, j, cnt = 0;
    for (i = 0; i < n; ++i) {
        parent[i] = i;
    }
    qsort(edges, m, sizeof(Edge), cmp);  // 排序
    for (i = 0; i < m; ++i) {
        int u = edges[i].u;
        int v = edges[i].v;
        if (find(u) != find(v)) {  // 判断是否形成环路
            printf("(%d, %d) %d\n", u, v, edges[i].w);
            union_set(u, v);  // 合并集合
            ++cnt;
            if (cnt == n - 1) {
                break;
            }
        }
    }
}

int main() {
    int n, m, i;
    Edge edges[MAX_EDGE_NUM];
    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(edges, n, m);
    return 0;
}

程序中使用结构体 `Edge` 表示一条边，其中 `u` 和 `v` 表示边的起点和终点，`w` 表示边的权重。使用数组 `parent` 存储并查集的父节点。函数 `find()` 和 `union_set()` 分别实现并查集的查找和合并操作。函数 `kruskal()` 实现克鲁斯卡尔算法求解最小生成树，具体实现如下：

1. 初始化并查集，并按照边权重从小到大排序所有的边。
2. 依次遍历排序后的边，如果该边连接的两个顶点不在同一个集合中，则将它们合并，并输出该边。
3. 当输出的边数达到 $n-1$ 时，算法结束。

在 `main()` 函数中，先读入图的节点数 `n` 和边数 `m`，然后读入每条边的起点、终点和权重。最后调用函数 `kruskal()` 求解最小生成树，并输出最小生成树的边集。