克鲁斯卡尔最小生成树C语言程序

克鲁斯卡尔算法是求解最小生成树的经典算法之一，其基本思想是从图中的所有边中选择权值最小的边，然后在剩余的边中继续选择权值最小的边，直到所有的节点都被遍历到。下面是一个使用C语言实现克鲁斯卡尔算法求解最小生成树的代码：

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

#define MAX_VERTEX_NUM 20
#define MAX_EDGE_NUM 100

typedef struct Edge {
    int from, to, weight;
} Edge;

typedef struct Graph {
    int vertex_num, edge_num;
    Edge edge[MAX_EDGE_NUM];
} Graph;

int parent[MAX_VERTEX_NUM];

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

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

void union_set(int x, int y) {
    int root_x = find_set(x);
    int root_y = find_set(y);
    if (root_x != root_y) {
        parent[root_x] = root_y;
    }
}

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

void kruskal(Graph *graph) {
    int i;
    for (i = 0; i < graph->vertex_num; i++) {
        make_set(i);
    }
    qsort(graph->edge, graph->edge_num, sizeof(Edge), cmp);
    int mst_weight = 0;
    for (i = 0; i < graph->edge_num; i++) {
        Edge e = graph->edge[i];
        if (find_set(e.from) != find_set(e.to)) {
            union_set(e.from, e.to);
            printf("%d -> %d : %d\n", e.from, e.to, e.weight);
            mst_weight += e.weight;
        }
    }
    printf("Minimum Spanning Tree Weight: %d\n", mst_weight);
}

int main() {
    Graph graph = {
        6,
        9,
        {
            {0, 1, 6},
            {0, 2, 1},
            {0, 3, 5},
            {1, 2, 5},
            {1, 4, 3},
            {2, 3, 5},
            {2, 4, 6},
            {2, 5, 4},
            {3, 5, 2}
        }
    };
    kruskal(&graph);
    return 0;
}

上述代码中，make_set、find_set和union_set分别实现了并查集的三个基本操作。在kruskal函数中，首先将所有边按照权值从小到大排序，然后依次遍历每条边，如果这条边的两个端点不在同一个连通块中，则将它们合并，并输出这条边的信息。最后输出最小生成树的总权值。