c++怎么实现最小生成树Kruskal算法_c++ 边权排序与并查集应用【案例】_技术教程

需先用std::sort按权值w升序排序边，再用带路径压缩和按秩合并的并查集实现Kruskal：遍历排序后边，若两端点不连通则合并并累加权值，选满n-1条边即停。

怎么用 `std::sort` 对边按权值升序排序

边必须先排好序，Kruskal 才能贪心地从小到大选边。C++ 中最直接的方式是把边存成 struct 或 tuple，然后传自定义比较函数给 std::sort。

推荐用 struct Edge { int u, v, w; };，语义清晰，避免 tuple 的位置混淆
比较函数要写成 lambda 或独立函数，不能只靠 operator（除非你重载了）
务必按 w 升序，否则算法失效；若权值相同，顺序不影响正确性，但可加次级排序避免潜在不稳定

struct Edge {
    int u, v, w;
};
vector edges;
// ... 添加边
sort(edges.begin(), edges.end(), [](const Edge& a, const Edge& b) {
    return a.w < b.w;
});

并查集（Union-Find）怎么写才不超时、不写错

Kruskal 的核心是快速判断两点是否已连通，并合并集合。手写并查集必须带路径压缩 + 按秩合并，否则在稀疏图上可能退化到 O(m log n) 甚至更差。

parent[i] 初始为 i，rank[i] 初始为 0（或用 size 启发式）
find(x) 必须递归/迭代做路径压缩，不能只返回根而不更新
unionSets(a, b) 要先 find 再比秩，不能直接对原始下标操作
注意：节点编号通常从 0 或 1 开始，初始化大小要对齐（比如 n+1）

struct UnionFind {
    vector parent, rank;
    UnionFind(int n) : parent(n), rank(n, 0) {
        iota(parent.begin(), parent.end(), 0);
    }
    int find(int x) {
        if (parent[x] != x) parent[x] = find(parent[x]);
        return parent[x];
    }
    void unite(int x, int y) {
        x = find(x), y = find(y);
        if (x == y) return;
        if (rank[x] < rank[y]) swap(x, y);
        parent[y] = x;
        if (rank[x] == rank[y]) rank[x]++;
    }
};

怎么组装 Kruskal 主循环：边遍历 + 并查集判环 + 累加权值

主逻辑极简：遍历已排序的边，对每条边 (u, v, w)，若 find(u) != find(v)，就合并并加进 MST；否则跳过（成环）。

用一个计数器 edges_used 控制何时退出：MST 只需 n-1 条边，满即停
不要在循环里反复调用 find 两次——先存结果再比较，避免冗余查找
注意图不连通时，循环结束但 edges_used ，此时应返回错误或特殊值（如 -1）
权值累加用 long long 更安全，尤其边权较大或边数多时

long long kruskal(int n, vector& edges) {
    sort(edges.begin(), edges.end(), [](auto& a, auto& b) { return a.w < b.w; });
    UnionFind uf(n);
    long long total = 0;
    int edges_used = 0;
    for (auto& e : edges) {
        int ru = uf.find(e.u), rv = uf.find(e.v);
        if (ru != rv) {
            uf.unite(ru, rv);
            total += e.w;
            if (++edges_used == n - 1) break;
        }
    }
    return edges_used == n - 1 ? total : -1;
}

常见错误：节点编号越界、并查集未初始化、边权类型不匹配

这些不是逻辑问题，而是上线就崩的硬伤。

输入节点编号是 1-indexed（比如题目说 “1 到 n”），但你开了 UnionFind(n) 却用 uf.find(e.u) 直接传入——若 e.u == n，下标就是 n，越界！应开 n+1 或统一转 0-indexed
UnionFind 构造时忘了 iota 或循环初始化 parent，导致所有 find 返回随机值
边权是 int，但总和存进 int total，溢出后变成负数，还误以为图不连通
排序时用了 a.w ，破坏严格弱序，std::sort 行为未定义