c++中如何实现Kruskal最小生成树_c++ Kruskal最小生成树实现方法-C++-PHP中文网

c++中如何实现Kruskal最小生成树_c++ Kruskal最小生成树实现方法

冰火之心

发布： 2025-09-27 15:04:01

原创

334人浏览过

Kruskal算法通过排序和并查集求最小生成树，先按权重排序边，再遍历选边并用并查集避免环，直到选出n-1条边。

c++中如何实现kruskal最小生成树_c++ kruskal最小生成树实现方法

Kruskal算法用于求解无向连通图的最小生成树，核心思想是按边的权重从小到大排序，依次选择边并确保不形成环，直到选够n-1条边（n为顶点数）。在C++中实现Kruskal算法，主要涉及边的排序和使用并查集（Union-Find）来检测环。

定义边结构与并查集

每条边包含起点、终点和权重。用结构体表示边，并重载比较函数以便排序。

struct Edge {
    int u, v, weight;
    bool operator<(const Edge& other) const {
        return weight < other.weight;
    }
};

登录后复制

并查集用于高效判断两个顶点是否在同一连通分量中，避免成环。

class UnionFind {
    vector<int> parent;
public:
    UnionFind(int n) {
        parent.resize(n);
        for (int i = 0; i < n; ++i) parent[i] = i;
    }
<pre class='brush:php;toolbar:false;'>int find(int x) {
    if (parent[x] != x)
        parent[x] = find(parent[x]);
    return parent[x];
}

void unite(int x, int y) {
    parent[find(x)] = find(y);
}

bool connected(int x, int y) {
    return find(x) == find(y);
}

登录后复制

};

立即学习“C++免费学习笔记（深入）”；

实现Kruskal主函数

将所有边存入容器，排序后逐个尝试加入生成树。使用并查集判断是否会产生环。

AI封面生成器

专业的AI封面生成工具，支持小红书、公众号、小说、红包、视频封面等多种类型，一键生成高质量封面图片。

108

查看详情

vector<Edge> kruskal(vector<Edge>& edges, int n) {
    sort(edges.begin(), edges.end());
    UnionFind uf(n);
    vector<Edge> result;
<pre class='brush:php;toolbar:false;'>for (const auto& e : edges) {
    if (!uf.connected(e.u, e.v)) {
        uf.unite(e.u, e.v);
        result.push_back(e);
        if (result.size() == n - 1) break;
    }
}
return result;

登录后复制

}

完整调用示例

假设图有4个节点，边如下：

int main() {
    vector<Edge> edges = {
        {0, 1, 10}, {0, 2, 6}, {0, 3, 5},
        {1, 3, 15}, {2, 3, 4}
    };
    int n = 4;
    vector<Edge> mst = kruskal(edges, n);
<pre class='brush:php;toolbar:false;'>cout << "最小生成树的边：\n";
for (const auto& e : mst) {
    cout << e.u << " -- " << e.v << " : " << e.weight << "\n";
}
return 0;

登录后复制

}

输出结果会显示构成最小生成树的边及其权重，总权重最小且无环。

基本上就这些。排序+并查集是Kruskal的关键，代码清晰且易于理解。

以上就是c++++中如何实现Kruskal最小生成树_c++ Kruskal最小生成树实现方法的详细内容，更多请关注php中文网其它相关文章！