最小生成树数据结构完整代码

根据提供的引用内容，我们可以了解到最小生成树是一个经典的算法问题，其中克鲁斯卡尔算法是其中一种实现方式。以下是一个用C++语言实现最小生成树的完整代码，其中包括了图的存储结构和克鲁斯卡尔算法的实现。

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

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

struct Edge {
    int u, v, w; // 边的起点、终点、权值
    bool operator < (const Edge& e) const {
        return w < e.w; // 按照权值从小到大排序
    }
} edges[MAXM];

int fa[MAXN]; // 并查集数组

int find(int x) { // 并查集查找
    if (fa[x] == x) return x;
    return fa[x] = find(fa[x]);
}

int main() {
    int n, m; // n为顶点数，m为边数
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        cin >> edges[i].u >> edges[i].v >> edges[i].w;
    }
    sort(edges, edges + m); // 对边按照权值排序
    for (int i = 1; i <= n; i++) {
        fa[i] = i; // 初始化并查集
    }
    int cnt = 0, ans = 0; // cnt为加入的边数，ans为最小生成树的权值和
    for (int i = 0; i < m; i++) {
        int u = edges[i].u, v = edges[i].v, w = edges[i].w;
        int x = find(u), y = find(v);
        if (x != y) { // 如果不在同一个连通块中
            fa[x] = y; // 合并连通块
            cnt++;
            ans += w;
            if (cnt == n - 1) break; // 边数达到n-1时退出
        }
    }
    cout << ans << endl; // 输出最小生成树的权值和
    return 0;
}