最小生成树—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
扫描二维码推送至手机访问。
版权声明：本文由青少年编程知识记录发布，如需转载请注明出处。
