kraskal算法求最小生成树用c语言

下面是 Kruskal 算法求最小生成树的 C 语言实现：

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

#define MAXN 1000  // 最大顶点数
#define MAXM 10000 // 最大边数

struct Edge {
    int u, v;   // 边的两个端点
    int w;      // 边的权值
} edges[MAXM];  // 存储所有边的数组

int parent[MAXN];   // 并查集数组，用来判断两个顶点是否在同一个连通块中

// 并查集的查找操作
int find(int x) {
    if (parent[x] == x) {
        return x;
    } else {
        return parent[x] = find(parent[x]);
    }
}

// 并查集的合并操作
void merge(int x, int y) {
    parent[find(x)] = find(y);
}

// 边的比较函数，根据权值从小到大排序
int cmp(const void* a, const void* b) {
    return ((struct Edge*)a)->w - ((struct Edge*)b)->w;
}

int main() {
    int n, m;   // n 个顶点，m 条边
    scanf("%d%d", &n, &m);

    // 读入所有边
    for (int i = 0; i < m; i++) {
        scanf("%d%d%d", &edges[i].u, &edges[i].v, &edges[i].w);
    }

    // 将所有边按权值从小到大排序
    qsort(edges, m, sizeof(struct Edge), cmp);

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

    int cnt = 0;    // 已选取的边的数量
    int ans = 0;    // 最小生成树的总权值

    // 依次选取每条边，如果它连接了两个不同的连通块，则加入最小生成树中
    for (int i = 0; i < m; i++) {
        int u = edges[i].u, v = edges[i].v, w = edges[i].w;
        if (find(u) != find(v)) {
            merge(u, v);
            ans += w;
            cnt++;
            if (cnt == n - 1) {
                break;
            }
        }
    }

    // 如果已选取的边的数量小于 n - 1，则说明原图不连通，不存在最小生成树
    if (cnt < n - 1) {
        printf("no minimum spanning tree\n");
    } else {
        printf("%d\n", ans);
    }

    return 0;
}

对于输入数据，第一行为顶点数 $n$ 和边数 $m$，接下来 $m$ 行每行三个整数 $u$、$v$ 和 $w$，表示一条边连接了顶点 $u$ 和 $v$，权值为 $w$。

程序的输出为最小生成树的总权值，如果原图不连通，则输出 `no minimum spanning tree`。