给定一个带权图求最小生成树代码c语言

以下是基于 Kruskal 算法的 C 代码实现，该算法的时间复杂度为 O(m*logm)：

#include<stdio.h>
#include<string.h>
#include<algorithm>

const int MAXN = 1005; // 最大点数
const int MAXM = 200005; // 最大边数
const int INF = 0x3f3f3f3f; // 无穷大

struct Edge {
    int u, v, w;
    bool operator < (const Edge& e) const {
        return w < e.w;
    }
} edges[MAXM];

int n, m; // 点数和边数
int fa[MAXN]; // 并查集数组
int ans; // 最小生成树的权值和

int find(int x) { // 并查集查找
    if (fa[x] == x) {
        return x;
    }
    return fa[x] = find(fa[x]);
}

void kruskal() {
    memset(fa, 0, sizeof(fa));
    for (int i = 1; i <= n; i++) {
        fa[i] = i;
    }
    std::sort(edges, edges + m);
    int cnt = 0;
    ans = 0;
    for (int i = 0; i < m; i++) {
        int u = edges[i].u, v = edges[i].v, w = edges[i].w;
        int x = find(u), y = find(v);
        if (x != y) {
            fa[x] = y;
            ans += w;
            cnt++;
            if (cnt == n - 1) {
                break;
            }
        }
    }
}

int main() {
    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);
    }
    kruskal();
    printf("%d\n", ans);
    return 0;
}

其中，edges[i].u, edges[i].v, edges[i].w 分别表示第 i 条边的起点、终点和边权值。Kruskal 算法的核心是将边按照权值从小到大排序，依次取出一条边，如果这条边的两个端点不在同一个连通块中，就将它们所在的连通块合并起来，并把这条边加入最小生成树。最终，所有边都被考虑完毕，算法结束。