C++语言 设计一个程序，对于下图所示的无向带权图G采用克鲁斯卡尔算法输出该图的最小生成树

好的，这是一个经典的最小生成树问题，下面是 C++ 代码实现 Kruskal 算法求解最小生成树：

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

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

bool cmp(Edge a, Edge b) {
    return a.w < b.w; // 按边的权值从小到大排序
}

const int N = 100010;

int p[N]; // 并查集数组，用于判断两个节点是否在同一个连通块中

int find(int x) {
    if (p[x] != x) p[x] = find(p[x]);
    return p[x];
}

int main() {
    int n, m;
    cin >> n >> m; // n 个点，m 条边

    vector<Edge> edges; // 存储边的信息

    for (int i = 0; i < m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        edges.push_back({u, v, w});
    }

    sort(edges.begin(), edges.end(), cmp); // 将边按权值从小到大排序

    for (int i = 1; i <= n; i++) p[i] = i; // 初始化并查集

    int cnt = 0; // 记录已经选取的边的数量
    int res = 0; // 记录最小生成树的权值和

    for (int i = 0; i < m; i++) {
        int u = edges[i].u, v = edges[i].v, w = edges[i].w;
        int pu = find(u), pv = find(v);
        if (pu != pv) { // 如果 u 和 v 不在同一个连通块中
            p[pu] = pv; // 合并 u 和 v 所在的连通块
            cnt++;
            res += w;
            if (cnt == n - 1) break; // 已经选取了 n-1 条边，退出循环
        }
    }

    cout << res << endl; // 输出最小生成树的权值和

    return 0;
}

该程序的时间复杂度为 $O(m\log m)$，其中 $m$ 表示边的数量。