c++中如何实现克鲁斯卡尔算法_c++ Kruskal算法代码实现_网络技术

Kruskal易错因排序失效和并查集未优化：边须权重前置或自定义比较，UF必须路径压缩，验证需检查选边数是否为n-1且图连通。

为什么直接写 `Kruskal` 常常连边都排不对？

因为 std::sort 默认按第一个字段升序，而你传的边结构体或 std::tuple 如果没重载比较或写错 compare，排序就失效。常见错误是把权重放在结构体第二个字段却没自定义排序规则，结果算法从最大边开始选，根本得不到最小生成树。

推荐统一用 std::vector<:tuple int>> 存边：权重在前，sort 自然按权重升序；或者用结构体 + lambda：

std::vector edges;
std::sort(edges.begin(), edges.end(), [](const Edge& a, const Edge& b) {
    return a.weight < b.weight;
});

并查集（`Union-Find`）不路径压缩会超时吗？

会。尤其点数 > 1e4 时，朴素 find 可能退化成 O(n) 单次查询，整体复杂度接近 O(mn)，Kruskal 就失去意义。必须做路径压缩 + 按秩合并（或只做路径压缩也够大多数 OJ 场景）。

关键实现要点：

parent[i] = i 初始化不能漏
find 中递归调用后要赋值更新：return parent[x] = find(parent[x])
unionSet 里判断的是 rootA != rootB，不是 a != b

struct UnionFind {
    std::vector parent, rank;
    UnionFind(int n) : parent(n), rank(n, 0) {
        for (int i = 0; i < n; ++i) parent[i] = i;
    }
    int find(int x) {
        return parent[x] == x ? x : parent[x] = find(parent[x]);
    }
    bool unionSet(int a, int b) {
        int ra = find(a), rb = find(b);
        if (ra == rb) return false;
        if (rank[ra] < rank[rb]) std::swap(ra, rb);
        parent[rb] = ra;
        if (rank[ra] == rank[rb]) rank[ra]++;
        return true;
    }
};

输入边时顶点编号从 0 还是 1 开始？

取决于题干。国内 OJ（如洛谷、PTA）多数用 1-indexed 顶点，但 UnionFind 类内部下标是 0-based，所以读入后立刻减 1，别等到排序或合并时再处理——容易忘、易出界、调试困难。

例如输入 u v w，统一转成：

int u, v, w;
std::cin >> u >> v >> w;
edges.emplace_back(w, u - 1, v - 1); // 权重前置，顶点归零

后续所有 unionSet(u-1, v-1)、find(u-1) 都基于 0-indexed，逻辑干净。

如何验证 Kruskal 输出的边确实构成 MST？

最简验证方式：检查是否恰好选了 n - 1 条边，且总权重与标准答案一致。更稳妥的做法是，在每次 unionSet 成功后记录该边，并确保最终 result.size() == n - 1；若提前结束（边用完但没凑够），说明图不连通——这时应返回错误或输出 -1，而不是强行输出部分结果。

典型收尾逻辑：

int cnt = 0, totalWeight = 0;
for (auto [w, u, v] : edges) {
    if (uf.unionSet(u, v)) {
        totalWeight += w;
        cnt++;
        if (cnt == n - 1) break;
    }
}
if (cnt != n - 1) {
    std::cout << "-1\n"; // 不连通
} else {
    std::cout << totalWeight << "\n";
}

注意：不要在循环外再查 uf.find(0) == uf.find(i) 判断连通性——Kruskal 过程中已隐含该信息，重复检查无必要且易错。

真正容易被忽略的是：当存在多条相同权重的边时，sort 的稳定性不影响正确性，但不同实现可能选出不同的 MST（只要总权相等就合法）。如果题目要求输出字典序最小的边集，就得在权重相同时按端点二次排序——这点几乎没人提，但现场笔试真会卡。

# edge # c++ # 为什么 # sort # 结构体 # union # 递归 # 循环 # Lambda # 算法 # 的是 # 升序 # 自定义 # 放在 # 第一个 # 没人 # 第二个 # 就得 # 而你

相关栏目：【网站优化151355 】【网络推广146373 】【网络技术251813 】【 AI营销90571 】