最小生成树c语言代码

以下是基于Kruskal算法实现的最小生成树C语言代码：

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

#define MAX_EDGES 1000
#define MAX_VERTICES 100

typedef struct {
    int u, v, w; // 边的两个顶点和边权值
} Edge;

Edge edges[MAX_EDGES];
int parent[MAX_VERTICES];
int rank[MAX_VERTICES];
int num_vertices, num_edges;

void make_set(int x) {
    parent[x] = x;
    rank[x] = 0;
}

int find_set(int x) {
    if (x != parent[x]) {
        parent[x] = find_set(parent[x]);
    }
    return parent[x];
}

void union_sets(int x, int y) {
    int root_x = find_set(x);
    int root_y = find_set(y);
    if (root_x == root_y) {
        return;
    }
    if (rank[root_x] < rank[root_y]) {
        parent[root_x] = root_y;
    } else if (rank[root_x] > rank[root_y]) {
        parent[root_y] = root_x;
    } else {
        parent[root_y] = root_x;
        rank[root_x]++;
    }
}

int cmp(const void* a, const void* b) {
    return ((Edge*)a)->w - ((Edge*)b)->w;
}

void kruskal() {
    int mst_weight = 0;
    for (int i = 0; i < num_vertices; i++) {
        make_set(i);
    }
    qsort(edges, num_edges, sizeof(Edge), cmp);
    for (int i = 0; i < num_edges; i++) {
        Edge e = edges[i];
        if (find_set(e.u) != find_set(e.v)) {
            union_sets(e.u, e.v);
            mst_weight += e.w;
        }
    }
    printf("Minimum spanning tree weight = %d\n", mst_weight);
}

int main() {
    scanf("%d %d", &num_vertices, &num_edges);
    for (int i = 0; i < num_edges; i++) {
        scanf("%d %d %d", &edges[i].u, &edges[i].v, &edges[i].w);
    }
    kruskal();
    return 0;
}

其中，make_set、find_set和union_sets函数是并查集的基本操作，cmp函数是为了在qsort函数中排序边的权值，kruskal函数是实现Kruskal算法的主要部分。

需要注意的是，这里使用了并查集来判断两个顶点是否处于同一个连通块中，从而避免了形成环路。同时，Kruskal算法还需要对边的权值进行排序，这里使用了标准库函数qsort来实现。