最小生成树—Kruskal（克鲁斯卡尔）算法
一、算法描述
在一个连通加权无向图中，找到一棵最小生成树。即，找到连接所有顶点的、权值总和最小的树，且树中不包含任何环。
二、核心思想
贪心策略：每次从未选择的边中，选取一条权值最小的边。
避免环路：如果加入这条边会导致生成树中形成环，则舍弃它。
集合管理：使用并查集数据结构来高效地判断两个顶点是否已经连通（即加入边是否会形成环）。
三、图解过程
假设我们有以下连通图 G，目标是找到它的最小生成树（MST）。
步骤 0：初始化
将图中所有边按权值从小到大排序。
初始化一个空的边集
MST，用于存放最小生成树的边。初始化并查集，让每个顶点自成一個集合。
排序后的边列表：(A,D):5, (C,E):5, (D,F):6, (A,B):7, (B,E):7, (B,C):8, (E,F):8, (B,D):9, ...
当前 MST： { }并查集状态： {A}, {B}, {C}, {D}, {E}, {F}
步骤 1：选择最小边 (A,D):5
检查：顶点 A 和 D 是否在同一集合？否（不会形成环）。
将边
(A,D)加入MST。在并查集中合并集合
{A}和{D}。
当前 MST： { (A,D):5 }并查集状态： {A, D}, {B}, {C}, {E}, {F}
步骤 2：选择下一条最小边 (C,E):5
检查：顶点 C 和 E 是否在同一集合？否（不会形成环）。
将边
(C,E)加入MST。合并集合
{C}和{E}。
当前 MST： { (A,D):5, (C,E):5 }并查集状态： {A, D}, {B}, {C, E}, {F}
步骤 3：选择边 (D,F):6
检查：顶点 D 和 F 是否在同一集合？否（D在
{A,D}，F在{F}）。将边
(D,F)加入MST。合并集合
{A, D}和{F}。
当前 MST： { (A,D):5, (C,E):5, (D,F):6 }并查集状态： {A, D, F}, {B}, {C, E}
步骤 4：选择边 (A,B):7
检查：顶点 A 和 B 是否在同一集合？否（A在
{A,D,F}，B在{B}）。将边
(A,B)加入MST。合并集合
{A, D, F}和{B}。
当前 MST： { (A,D):5, (C,E):5, (D,F):6, (A,B):7 }并查集状态： {A, B, D, F}, {C, E}
步骤 5：选择边 (B,E):7
关键检查：顶点 B 和 E 是否在同一集合？
B 在
{A, B, D, F}E 在
{C, E}不在同一集合（不会形成环）。
将边
(B,E)加入MST。合并两个大集合
{A, B, D, F}和{C, E}。此时所有顶点都在同一个集合中。
当前 MST： { (A,D):5, (C,E):5, (D,F):6, (A,B):7, (B,E):7 }并查集状态： {A, B, C, D, E, F}
算法终止
终止条件：
MST中的边数 = 顶点数 - 1 = 5。我们已经找到了最小生成树。后续的边
(B,C):8,(E,F):8,(B,D):9等不再被考虑，因为加入它们都会连接已经连通的顶点，从而形成环。
最终的最小生成树（MST） 如上图红色边所示。总权值 = 5 + 5 + 6 + 7 + 7 = 30
关键要点总结
贪心选择：始终选择当前可用的、不构成环的最小权边。
环检测工具：并查集是高效实现 Kruskal 算法的关键，它能近乎 O(1) 时间完成“查找”和“合并”操作。
时间复杂度：
排序边：O(|E| log |E|)，其中 |E| 是边数。
并查集操作：近似 O(|E| α(|V|))，其中 α 是增长极慢的反阿克曼函数。
总复杂度主要取决于排序：O(|E| log |E|)。
适用场景：适用于稀疏图（边数 |E| 远小于顶点数 |V|² 的图），因为其复杂度主要由边数决定。
【参考代码】
#include <iostream> #include <vector> #include <algorithm> using namespace std; // 边的结构体 struct Edge { int u; int v; int weight; }; // 并查集结构体 struct UnionFind { vector<int> parent; vector<int> rank; }; // 初始化并查集 void initUnionFind(UnionFind& uf, int n) { uf.parent.resize(n); uf.rank.resize(n, 0); for (int i = 0; i < n; ++i) { uf.parent[i] = i; } } // 查找操作 int find(UnionFind& uf, int x) { if (uf.parent[x] != x) { uf.parent[x] = find(uf, uf.parent[x]); } return uf.parent[x]; } // 合并操作 bool merge(UnionFind& uf, int x, int y) { int rootX = find(uf, x); int rootY = find(uf, y); if (rootX == rootY) return false; if (uf.rank[rootX] < uf.rank[rootY]) { uf.parent[rootX] = rootY; } else if (uf.rank[rootX] > uf.rank[rootY]) { uf.parent[rootY] = rootX; } else { uf.parent[rootY] = rootX; uf.rank[rootX]++; } return true; } // 比较函数 bool cmp(Edge a, Edge b) { return a.weight < b.weight; } // Kruskal算法 vector<Edge> kruskalMST(int n, vector<Edge>& edges) { // 1. 按边权升序排序 sort(edges.begin(), edges.end(), cmp); // 2. 初始化并查集 UnionFind uf; initUnionFind(uf, n); // 3. 构建最小生成树 vector<Edge> mst; int mstWeight = 0; for (size_t i = 0; i < edges.size(); ++i) { const Edge& edge = edges[i]; if (merge(uf, edge.u, edge.v)) { mst.push_back(edge); mstWeight += edge.weight; if (mst.size() == (size_t)(n - 1)) break; } } cout << "最小生成树总权重: " << mstWeight << endl; return mst; } int main() { int n = 6; vector<Edge> edges; // 添加边 edges.push_back({0, 1, 4}); edges.push_back({0, 2, 4}); edges.push_back({1, 2, 2}); edges.push_back({2, 3, 3}); edges.push_back({2, 5, 2}); edges.push_back({2, 4, 4}); edges.push_back({3, 4, 3}); edges.push_back({4, 5, 3}); vector<Edge> mst = kruskalMST(n, edges); cout << "最小生成树包含的边:" << endl; for (size_t i = 0; i < mst.size(); ++i) { const Edge& edge = mst[i]; cout << edge.u << " - " << edge.v << " : " << edge.weight << endl; } return 0; }输出
最小生成树总权重: 14 最小生成树包含的边: 1 - 2 : 2 2 - 5 : 2 2 - 3 : 3 3 - 4 : 3 0 - 1 : 4