用kruskal算法构造最小生成树c语言

Kruskal算法是一种常用的构造最小生成树的算法，其基本思想是从小到大选择边，直到选出n-1条边为止。下面是C语言实现Kruskal算法构造最小生成树的代码：

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

#define MAX_VERTICES 1000
#define MAX_EDGES 10000

typedef struct edge {
    int u, v, w;
} Edge;

int parent[MAX_VERTICES];
int rank[MAX_VERTICES];

Edge edges[MAX_EDGES];
Edge mst[MAX_EDGES];

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_set(int x, int y) {
    int px = find_set(x);
    int py = find_set(y);
    if (rank[px] > rank[py]) {
        parent[py] = px;
    } else {
        parent[px] = py;
        if (rank[px] == rank[py]) {
            rank[py]++;
        }
    }
}

int compare(const void *a, const void *b) {
    Edge *ea = (Edge *) a;
    Edge *eb = (Edge *) b;
    return ea->w - eb->w;
}

void kruskal() {
    int i, j = 0;
    for (i = 0; i < num_vertices; i++) {
        make_set(i);
    }
    qsort(edges, num_edges, sizeof(Edge), compare);
    for (i = 0; i < num_edges && j < num_vertices - 1; i++) {
        Edge e = edges[i];
        int u = e.u;
        int v = e.v;
        if (find_set(u) != find_set(v)) {
            union_set(u, v);
            mst[j++] = e;
        }
    }
}

int main() {
    int i;
    scanf("%d %d", &num_vertices, &num_edges);
    for (i = 0; i < num_edges; i++) {
        scanf("%d %d %d", &edges[i].u, &edges[i].v, &edges[i].w);
    }
    kruskal();
    printf("Minimum Spanning Tree:\n");
    for (i = 0; i < num_vertices - 1; i++) {
        printf("%d %d %d\n", mst[i].u, mst[i].v, mst[i].w);
    }
    return 0;
}

在这个实现中，我们使用了一个Edge结构体来表示边，其中包括起点、终点和边权。我们使用了并查集来判断是否形成环，使用了快速排序算法对所有边按照边权从小到大排序。最后，我们输出构造出的最小生成树。