最小生成树(Minimum Spanning Tree, MST)是图论中的一个重要概念，指在一个连通加权无向图中，找到一棵包含所有顶点的生成树，且这棵树所有边的权值之和最小。最小生成树在实际中有广泛应用，如网络设计、电路布线、交通规划等领域。
一、最小生成树的基本性质
- 定义：对于连通加权无向图G=(V,E)，最小生成树T是G的一个子图，满足：
• 包含G的所有顶点
• 是一棵树（无环且连通）
• 所有边的权值之和最小 - 性质：
• 环切分性质：图中任意环，删除权值最大的边后，剩余边仍构成生成树
• 边选择性质：若边是连接两个子树的最小权边，则该边必属于某棵MST
• 唯一性：当所有边权值不相同时，MST唯一；否则可能存在多个MST
二、经典算法
1. Prim算法（普里姆算法）
基本思想：从顶点出发，逐步扩展生成树，每次选择连接生成树与非生成树顶点的最小权边。
算法步骤：
- 任选一个起始顶点加入生成树
- 在所有连接生成树与非生成树顶点的边中，选择权值最小的边加入生成树
- 将新顶点加入生成树集合
- 重复步骤2-3，直到所有顶点都加入生成树
时间复杂度：
- 邻接矩阵实现：O(V²)
- 二叉堆优化：O(E log V)
- 斐波那契堆优化：O(E + V log V)
C++实现：
int prim(vector<vector<pair<int, int>>>& graph, int start) {
int n = graph.size();
vector<int> dist(n, INT_MAX);
vector<bool> visited(n, false);
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq;
dist[start] = 0;
pq.push({0, start});
int total = 0;
while (!pq.empty()) {
auto [d, u] = pq.top(); pq.pop();
if (visited[u]) continue;
visited[u] = true;
total += d;
for (auto [v, w] : graph[u]) {
if (!visited[v] && w < dist[v]) {
dist[v] = w;
pq.push({w, v});
}
}
}
return total;
}
2. Kruskal算法（克鲁斯卡尔算法）
基本思想：按边权值从小到大排序，依次选择不形成环的边加入生成树。
算法步骤：
- 将所有边按权值从小到大排序
- 初始化并查集数据结构
- 依次检查每条边，如果边的两个端点不在同一集合，则加入生成树并合并集合
- 重复步骤3直到生成树包含V-1条边
时间复杂度：
- 排序主导：O(E log E)
- 并查集操作：近似O(α(V))
- 总复杂度：O(E log E)
C++实现：
struct DSU {
vector<int> parent;
DSU(int n) : parent(n) { iota(parent.begin(), parent.end(), 0); }
int find(int x) { return parent[x] == x ? x : parent[x] = find(parent[x]); }
bool unite(int x, int y) {
x = find(x), y = find(y);
if (x == y) return false;
parent[y] = x;
return true;
}
};
int kruskal(vector<vector<int>>& edges, int n) {
sort(edges.begin(), edges.end(), [](auto& a, auto& b) { return a[2] < b[2]; });
DSU dsu(n);
int total = 0, count = 0;
for (auto& e : edges) {
if (dsu.unite(e[0], e[1])) {
total += e[2];
if (++count == n - 1) break;
}
}
return count == n - 1 ? total : -1;
}
三、算法比较与选择
| 特性 | Prim算法 | Kruskal算法 |
|---|---|---|
| 思想 | 顶点扩展 | 边选择 |
| 数据结构 | 优先队列 | 并查集+排序 |
| 时间复杂度 | O(E log V) | O(E log E) |
| 适用场景 | 稠密图 | 稀疏图 |
| 实现难度 | 中等 | 较简单 |
选择建议：
- 当图较稠密（E≈V²）时，Prim算法更高效
- 当图较稀疏（E≈V）时，Kruskal算法更合适
- 需要动态维护生成树时，Prim算法更方便
四、应用实例
- 网络设计：在多个城市间建立通信网络，最小化布线成本
- 电路设计：连接多个元件，最小化导线总长度
- 聚类分析：基于相似度构建层次聚类结构
- 图像分割：将图像像素连接成区域
