C语言写一段代码：输入一个带权图，用克鲁斯卡尔算法，求其最小生成树

好的，以下是C语言实现克鲁斯卡尔算法求最小生成树的代码：

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

#define MAX_VERTEX_NUM 100 // 最大顶点数
#define MAX_EDGE_NUM (MAX_VERTEX_NUM*(MAX_VERTEX_NUM-1)/2) // 最大边数

typedef struct {
    int begin; // 边的起点
    int end; // 边的终点
    int weight; // 边的权值
} Edge;

// 定义并查集结构体
typedef struct {
    int parent[MAX_VERTEX_NUM]; // 记录每个节点的父节点
    int rank[MAX_VERTEX_NUM]; // 记录每个节点的秩
} UnionFindSet;

// 初始化并查集
void MakeSet(UnionFindSet* set, int size) {
    for (int i = 0; i < size; i++) {
        set->parent[i] = i;
        set->rank[i] = 0;
    }
}

// 查找节点所在集合的代表元
int Find(UnionFindSet* set, int x) {
    if (x != set->parent[x]) {
        set->parent[x] = Find(set, set->parent[x]); // 路径压缩
    }
    return set->parent[x];
}

// 合并两个集合
void Union(UnionFindSet* set, int x, int y) {
    int xRoot = Find(set, x);
    int yRoot = Find(set, y);
    if (xRoot == yRoot) return;
    if (set->rank[xRoot] > set->rank[yRoot]) {
        set->parent[yRoot] = xRoot;
    } else if (set->rank[xRoot] < set->rank[yRoot]) {
        set->parent[xRoot] = yRoot;
    } else {
        set->parent[yRoot] = xRoot;
        set->rank[xRoot]++;
    }
}

// 按边的权值从小到大排序
void SortEdges(Edge* edges, int edgeNum) {
    for (int i = 0; i < edgeNum - 1; i++) {
        for (int j = 0; j < edgeNum - 1 - i; j++) {
            if (edges[j].weight > edges[j+1].weight) {
                Edge temp = edges[j];
                edges[j] = edges[j+1];
                edges[j+1] = temp;
            }
        }
    }
}

// 克鲁斯卡尔算法求最小生成树
void Kruskal(Edge* edges, int vertexNum, int edgeNum) {
    UnionFindSet set;
    MakeSet(&set, vertexNum);
    SortEdges(edges, edgeNum);
    printf("最小生成树的边为：\n");
    for (int i = 0; i < edgeNum; i++) {
        int begin = edges[i].begin;
        int end = edges[i].end;
        if (Find(&set, begin) != Find(&set, end)) {
            Union(&set, begin, end);
            printf("%d %d %d\n", begin, end, edges[i].weight);
        }
    }
}

int main() {
    int vertexNum, edgeNum;
    Edge edges[MAX_EDGE_NUM];
    printf("请输入顶点数和边数：\n");
    scanf("%d %d", &vertexNum, &edgeNum);
    printf("请输入每条边的起点、终点和权值：\n");
    for (int i = 0; i < edgeNum; i++) {
        scanf("%d %d %d", &edges[i].begin, &edges[i].end, &edges[i].weight);
    }
    Kruskal(edges, vertexNum, edgeNum);
    return 0;
}

以上代码实现了克鲁斯卡尔算法求最小生成树，其中用到了并查集来判断两个节点是否在同一个集合中，以及路径压缩和秩的优化来提高并查集的效率。