用C语言写克鲁斯卡尔算法数据结构

克鲁斯卡尔算法是一种解决最小生成树问题的算法，可以用来求解带权连通图的最小生成树。下面是使用C语言实现克鲁斯卡尔算法的数据结构代码：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX_VERTEX_NUM 100 // 最大顶点数
#define MAX_EDGE_NUM (MAX_VERTEX_NUM * (MAX_VERTEX_NUM - 1) / 2) // 最大边数

// 边的结构体
struct Edge {
    int start; // 起点
    int end; // 终点
    int weight; // 权值
};

// 图的结构体
struct Graph {
    int n; // 顶点数
    int m; // 边数
    struct Edge edges[MAX_EDGE_NUM]; // 存储边的数组
};

// 并查集
int fa[MAX_VERTEX_NUM];

// 比较函数
int cmp(const void *a, const void *b) {
    return ((struct Edge *)a)->weight - ((struct Edge *)b)->weight;
}

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

// 查找根节点
int find_set(int x) {
    if (fa[x] == x) {
        return x;
    }
    return fa[x] = find_set(fa[x]);
}

// 合并集合
void merge(int x, int y) {
    fa[find_set(x)] = find_set(y);
}

// 克鲁斯卡尔算法
void kruskal(struct Graph *g) {
    int cnt = 0; // 记录加入的边数
    int ans = 0; // 记录最小生成树的权值和
    init_union_find(g->n); // 初始化并查集
    qsort(g->edges, g->m, sizeof(struct Edge), cmp); // 对边按权值排序
    for (int i = 0; i < g->m; i++) {
        int start = g->edges[i].start;
        int end = g->edges[i].end;
        int weight = g->edges[i].weight;
        if (find_set(start) != find_set(end)) { // 如果不在同一个集合中
            merge(start, end); // 合并集合
            cnt++; // 边数加一
            ans += weight; // 权值和增加
            if (cnt == g->n - 1) { // 边数等于顶点数减一，说明已经构成了最小生成树
                break;
            }
        }
    }
    printf("The weight of the minimum spanning tree is: %d\n", ans);
}

int main() {
    struct Graph g = {6, 9, {{1, 2, 6}, {1, 3, 1}, {1, 4, 5}, {2, 3, 5}, {2, 5, 3}, {3, 4, 5}, {3, 5, 6}, {3, 6, 4}, {4, 6, 2}}};
    kruskal(&g);
    return 0;
}

以上代码实现了克鲁斯卡尔算法，其中包括了并查集的实现。您可以根据需要修改顶点数、边数以及边的具体信息。