简介
克鲁斯卡尔算法是一种经典的贪心算法，用于解决加权无向图中的最小生成树问题。该算法致力于构建一棵包含图中所有顶点的树，同时确保树中边的总权重最小。在 C++ 中实现克鲁斯卡尔算法相对简单，但有几种优化可以显著提高其效率。
实现
基本实现
以下是最基本的克鲁斯卡尔算法实现：
include
include
include using namespace std;Struct Edge {int u, v, w; // u 和 v 是端点，w 是权重
};bool compare(const Edge& a, const Edge& b) {return a.w < b.w; // 根据权重从小到大排序
}int find(vector& parent, int u) {if (parent[u] != u) {parent[u] = find(parent, parent[u]);}return parent[u];
}int unite(vector& parent, vector& rank, int u, int v) {int uroot = find(parent, u);int vroot = find(parent, v);if (uroot != vroot) {if (rank[uroot] < rank[vroot]) {parent[uroot] = vroot;} else if (rank[uroot] > rank[vroot]) {parent[vroot] = uroot;} else {parent[vroot] = uroot;rank[uroot]++;}}
}int kruskal(vector& edges, int n) {vector parent(n);vector
include
include
include using namespace std;struct Edge {int u, v, w; // u 和 v 是端点，w 是权重
};bool compare(const Edge& a, const Edge& b) {return a.w < b.w; // 根据权重从小到大排序
}class DSU {
private:vector parent;vector rank;public:DSU(int n) {parent.resize(n);rank.resize(n, 0);for (int i = 0; i < n; i++) {parent[i] = i;}}int find(int u) {if (parent[u] != u) {parent[u] = find(parent[u]);}return parent[u];}int unite(int u, int v) {int uroot = find(u);int vroot = find(v);if (uroot != vroot) {if (rank[uroot] < rank[vroot]) {parent[uroot] = vroot;} else if (rank[uroot] > rank[vroot]) {parent[vroot] = uroot;} else {parent[vroot] = uroot;rank[uroot]++;}}}
};int kruskal(vector& edges, int n) {DSU dsu(n);sort(edges.begin(), edges.end(), compare); // 按权重从小到大排序int total_weight = 0;for (auto edge : edges) {int u = edge.u;
int v = edge.v;int w = edge.w;int uroot = dsu.find(u);int vroot = dsu.find(v);
相关标签：
C、
ke、
c、
深入探讨其实现和优化、
中的克鲁斯卡尔算法、
上一篇：克鲁斯卡尔算法在实际应用中的案例研究网络
下一篇：用Python实现克鲁斯卡尔算法逐步指南和代码
