最小生成树kruskal算法数据结构C语言完整代码

以下是C语言实现Kruskal算法求解最小生成树的完整代码，其中包括数据结构的定义和算法的实现：

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

#define MAX_VERTEX_NUM 100 // 最大顶点数
#define MAX_EDGE_NUM 100 // 最大边数

// 定义边的结构体
typedef struct {
    int u; // 边的起点
    int v; // 边的终点
    int w; // 边的权值
} Edge;

// 定义并查集结构体
typedef struct {
    int parent[MAX_VERTEX_NUM]; // 父节点数组
    int rank[MAX_VERTEX_NUM]; // 秩数组
} UnionFindSet;

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

// 查找节点所在集合的根节点
int Find(UnionFindSet *S, int x) {
    if (S->parent[x] != x) {
        S->parent[x] = Find(S, S->parent[x]);
    }
    return S->parent[x];
}

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

// Kruskal算法求解最小生成树
void Kruskal(Edge *E, int n, int m) {
    UnionFindSet S;
    MakeSet(&S, n);
    int count = 0;
    for (int i = 0; i < m; i++) {
        int u = E[i].u;
        int v = E[i].v;
        int w = E[i].w;
        if (Find(&S, u) != Find(&S, v)) {
            printf("(%d, %d) %d\n", u, v, w);
            Union(&S, u, v);
            count++;
            if (count == n - 1) {
                break;
            }
        }
    }
}

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