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

好的，这是一个简单的 C 语言代码示例，用于使用克鲁斯卡尔算法求解给定图的最小生成树。

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

// 定义边的数据结构
struct Edge {
    int u, v, w;
};

// 定义并查集数据结构
struct UnionFind {
    int* parent;
    int* rank;
};

struct UnionFind* createUnionFind(int n) {
    struct UnionFind* uf = (struct UnionFind*) malloc(sizeof(struct UnionFind));
    uf->parent = (int*) malloc(n * sizeof(int));
    uf->rank = (int*) malloc(n * sizeof(int));
    for (int i = 0; i < n; i++) {
        uf->parent[i] = i;
        uf->rank[i] = 0;
    }
    return uf;
}

void destroyUnionFind(struct UnionFind* uf) {
    free(uf->parent);
    free(uf->rank);
    free(uf);
}

int find(struct UnionFind* uf, int x) {
    if (uf->parent[x] != x) {
        uf->parent[x] = find(uf, uf->parent[x]);
    }
    return uf->parent[x];
}

void unionSet(struct UnionFind* uf, int x, int y) {
    int root_x = find(uf, x);
    int root_y = find(uf, y);
    if (root_x == root_y) {
        return;
    }
    if (uf->rank[root_x] < uf->rank[root_y]) {
        uf->parent[root_x] = root_y;
    } else if (uf->rank[root_x] > uf->rank[root_y]) {
        uf->parent[root_y] = root_x;
    } else {
        uf->parent[root_y] = root_x;
        uf->rank[root_x]++;
    }
}

// 克鲁斯卡尔算法求解最小生成树
struct Edge* kruskal(int n, struct Edge* edges, int m, int* resSize) {
    struct UnionFind* uf = createUnionFind(n);
    struct Edge* res = (struct Edge*) malloc((n - 1) * sizeof(struct Edge));
    int count = 0;
    *resSize = 0;
    // 对边按权值从小到大排序
    qsort(edges, m, sizeof(struct Edge), [](const void* a, const void* b) -> int {
        return ((struct Edge*) a)->w - ((struct Edge*) b)->w;
    });
    // 遍历边，将不在同一个集合中的端点合并并添加到结果中
    for (int i = 0; i < m && count < n - 1; i++) {
        int u = edges[i].u, v = edges[i].v, w = edges[i].w;
        if (find(uf, u) != find(uf, v)) {
            unionSet(uf, u, v);
            res[(*resSize)++] = edges[i];
            count++;
        }
    }
    destroyUnionFind(uf);
    return res;
}

// 测试用例
int main() {
    int n = 5;
    struct Edge edges[] = {
        {0, 1, 2},
        {0, 3, 6},
        {1, 3, 8},
        {1, 2, 3},
        {1, 4, 5},
        {2, 4, 7},
        {3, 4, 9}
    };
    int m = sizeof(edges) / sizeof(edges[0]);
    int resSize;
    struct Edge* res = kruskal(n, edges, m, &resSize);
    for (int i = 0; i < resSize; i++) {
        printf("%d %d %d\n", res[i].u, res[i].v, res[i].w);
    }
    free(res);
    return 0;
}

这个程序可以处理具有 n 个顶点和 edges 数组中给定的 m 条边的无向图，其中每条边都由其两个端点和权重表示。程序使用并查集数据结构来维护连通性。它首先将边按权重从小到大排序，然后从最小的边开始遍历，如果两个端点不在同一个集合中，则将它们合并并添加到结果数组中。最后，程序返回包含最小生成树的边的数组。

希望这个示例对你有所帮助！