什么是最小生成树
在连通加权无向图 G=(V, E) 中，最小生成树（Minimum Spanning Tree, MST）是 G 的一个子图，满足：
- 包含 G 的所有顶点；
- 是一棵树（无环且连通）；
- 所有边的权值之和最小。
应用场景：网络布线、电路设计、交通规划、聚类分析等一切”用最少的连接代价把所有节点连起来”的问题。
关键性质
- 环切分性质：任意环中权值最大的边一定不属于某棵 MST；
- 边选择性质：连接两个不同连通分量的最小权边，必属于某棵 MST（两个经典算法的正确性都建立在它之上）；
- 唯一性：所有边权值互不相同时 MST 唯一；有权值相同边时可能存在多棵。
Prim 算法（加点）
从某个顶点出发，维护”已选集合”，每一步选择连接集合内外的最小权边，把新顶点并入集合，直到覆盖全部顶点。
C++ 实现（优先队列优化，O(E log V)）
int prim(vector<vector<pair<int,int>>>& graph, int start) {
int n = graph.size();
vector<int> dist(n, INT_MAX);
vector<bool> inTree(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 (inTree[u]) continue;
inTree[u] = true;
total += d;
for (auto [v, w] : graph[u]) {
if (!inTree[v] && w < dist[v]) {
dist[v] = w;
pq.push({w, v});
}
}
}
return total;
}
复杂度：邻接矩阵 O(V²)；二叉堆优化 O(E log V)；斐波那契堆 O(E + V log V)。稠密图（E ≈ V²）用 Prim 更合适。
Kruskal 算法（加边）
把所有边按权值从小到大排序，用并查集维护连通性，依次加入”两个端点尚不连通”的边，直到生成树包含 V−1 条边。
C++ 实现（O(E log E)）
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, cnt = 0;
for (auto& e : edges) {
if (dsu.unite(e[0], e[1])) {
total += e[2];
if (++cnt == n - 1) break;
}
}
return cnt == n - 1 ? total : -1; // 不足 V-1 条边说明图不连通
}
复杂度由排序主导：O(E log E)；并查集操作近似常数。稀疏图（E ≈ V）用 Kruskal 更合适。
算法对比与选型
| 特性 | Prim | Kruskal |
|---|---|---|
| 思想 | 顶点逐步扩展 | 边按权排序选取 |
| 依赖结构 | 优先队列（或堆） | 并查集 + 排序 |
| 时间复杂度 | O(E log V) | O(E log E) |
| 适用图 | 稠密图 | 稀疏图 |
| 实现难度 | 中等 | 较简单 |
选型建议：边很多（稠密）选 Prim；边较少（稀疏）或边以”三元组列表”给出选 Kruskal；需要在线动态维护生成树时 Kruskal 思路更直观。特别注意：Kruskal 返回 -1 分支（图不连通）是容易漏写的边界。
