c语言用克鲁斯卡尔算法实现图的最小生成树

克鲁斯卡尔算法是一种基于贪心思想的图论算法，用于求解一个带权无向图的最小生成树。

以下是用C语言实现克鲁斯卡尔算法求解图的最小生成树的基本步骤：

1. 定义一个结构体来表示边，包含边的起点、终点和边权值。

struct Edge {
    int u, v, w; // 起点、终点和边权值
};

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

int fa[MAXN]; // 并查集数组，用于存储每个节点所在的连通块的根节点

void init(int n) { // 初始化并查集
    for (int i = 1; i <= n; i++) {
        fa[i] = i;
    }
}

int find(int x) { // 查找x所在的连通块的根节点
    if (fa[x] == x) {
        return x;
    }
    return fa[x] = find(fa[x]);
}

void merge(int x, int y) { // 合并x和y所在的连通块
    fa[find(x)] = find(y);
}

3. 定义一个边的比较函数，用于将所有边按照权值从小到大排序。

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

4. 定义一个函数，用于求解最小生成树。

void kruskal(int n, int m, Edge edges[]) { // n为节点数，m为边数，edges为边数组
    int cnt = 0; // 计数器，用于统计已经加入最小生成树中的边数
    int ans = 0; // 最小生成树的权值和
    init(n); // 初始化并查集
    qsort(edges, m, sizeof(Edge), cmp); // 将所有边按照权值从小到大排序
    for (int i = 0; i < m; i++) { // 枚举所有边
        int u = edges[i].u, v = edges[i].v, w = edges[i].w;
        if (find(u) != find(v)) { // 如果u和v不在同一个连通块中，则将它们加入最小生成树中
            merge(u, v); // 合并u和v所在的连通块
            ans += w; // 计算最小生成树的权值和
            cnt++; // 统计已经加入最小生成树中的边数
            if (cnt == n - 1) { // 如果已经加入n-1条边，则最小生成树已经构造完成
                break;
            }
        }
    }
    printf("%d\n", ans); // 输出最小生成树的权值和
}

完整代码如下：