c语言中kruskal算法构造最小生成树给出构造过程

Kruskal算法是一种用来解决最小生成树问题的贪心算法。它的基本思想是将图中的所有边按照权值的大小从小到大排序，然后依次选择权值最小的边，并将其加入到生成树中，直到所有的节点都被覆盖为止。

下面是使用C语言实现Kruskal算法构造最小生成树的一般步骤：

1. 定义结构体存储边的信息，包括起点、终点和权值。

    typedef struct Edge{
        int u; // 起点
        int v; // 终点
        int w; // 权值
    }Edge;

2. 定义比较函数，用于对边按照权值从小到大排序。

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

3. 对边按照权值从小到大排序。

    qsort(edges, m, sizeof(Edge), cmp);

4. 定义并查集，用于判断两个节点是否在同一个连通块中。

    int fa[N];
    void init(){
        for(int i = 1; i <= n; i++){
            fa[i] = i;
        }
    }
    int find(int x){
        if(fa[x] == x) return x;
        else return fa[x] = find(fa[x]);
    }

5. 遍历所有的边，如果两个节点不在同一个连通块中，则选择该边，并将两个节点合并到同一个连通块中。

    int ans = 0; // 最小生成树的权值和
    for(int i = 0; i < m; i++){
        int u = edges[i].u;
        int v = edges[i].v;
        int w = edges[i].w;
        int fu = find(u);
        int fv = find(v);
        if(fu != fv){
            fa[fu] = fv;
            ans += w;
        }
    }

完整代码如下：