c++实现克鲁斯卡尔算法

克鲁斯卡尔算法是一种求解最小生成树的贪心算法，其基本思想是按照边的权值从小到大排序，依次选择权值最小且不构成环的边加入生成树中，直到生成树中有 n-1 条边为止。下面是 C++ 实现克鲁斯卡尔算法的示例代码：

#include <iostream>
#include <algorithm>
using namespace std;

const int MAXN = 1000;  // 最大顶点数
const int MAXM = 10000; // 最大边数

int n, m;               // 顶点数和边数
int fa[MAXN];           // 并查集数组
struct edge {
    int u, v, w;        // 边的起点、终点和权值
} e[MAXM];              // 存储边的数组

bool cmp(edge a, edge b) {  // 排序函数，按边权升序排序
    return a.w < b.w;
}

int find(int x) {  // 并查集查找函数
    return fa[x] == x ? x : fa[x] = find(fa[x]);
}

int kruskal() {     // 克鲁斯卡尔算法函数
    int ans = 0, cnt = 0;
    for (int i = 1; i <= n; ++i) fa[i] = i;  // 初始化并查集
    sort(e + 1, e + m + 1, cmp);  // 对边按权值升序排序
    for (int i = 1; i <= m; ++i) {  // 枚举所有边
        int u = find(e[i].u), v = find(e[i].v);
        if (u != v) {  // 如果不在同一个连通块中
            fa[u] = v;  // 合并连通块
            ans += e[i].w;  // 计算最小生成树的权值
            ++cnt;
            if (cnt == n - 1) break;  // 边数达到最大值，退出循环
        }
    }
    return ans;
}

int main() {
    cin >> n >> m;
    for (int i = 1; i <= m; ++i) {
        cin >> e[i].u >> e[i].v >> e[i].w;
    }
    int ans = kruskal();
    cout << ans << endl;
    return 0;
}

在该程序中，使用结构体 `edge` 存储边的起点、终点和权值，使用并查集维护连通块，使用排序函数 `cmp` 将边按权值升序排序，使用函数 `kruskal` 实现克鲁斯卡尔算法，并返回最小生成树的权值。在主函数中，输入顶点数和边数，读入边的信息，调用函数 `kruskal`，输出最小生成树的权值。