Kruskal算法通过排序和并查集求最小生成树，先按权重排序边，再遍历选边并用并查集避免环，直到选出n-1条边。
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主函数
将所有边存入容器，排序后逐个尝试加入生成树。使用并查集判断是否会产生环。
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的关键，代码清晰且易于理解。
