核心逻辑与数学原理
Kruskal 算法虽然在稀疏图中表现优异，但在完全图或极稠密图（边数 $M \approx N^2$）中，其排序的时间开销 $O(M \log M)$ 会发生灾难性膨胀。而基于点集拓扑扩张的 Prim 算法，其状态转移的核心不依赖于全局边的排序，因此在稠密图场景下拥有统治级的时空优势。
1. 割边定理与切分空间（Cut Property）
Prim 算法的正确性严格建立在图论的割边定理之上：
- 数学定义：设无向连通图 $G=(V, E)$ 的顶点集 $V$ 被任意切分为两个不相交的非空子集：已加入最小生成树的点集 $S$（蓝点集）与未加入树的点集 $V-S$（白点集）。
- 定理内容：在所有连接 $S$ 与 $V-S$ 的跨越边（即一端在 $S$ 中，另一端在 $V-S$ 中）中，权值最小的那条边必然属于该图的某棵最小生成树。
2. 状态转移的两种物理实现
根据图的规模，Prim 算法有两种截然不同的状态维护方式：
方案甲：朴素 Prim 算法（针对极稠密图 $M \approx N^2$）
直接使用邻接矩阵存储图。每一轮通过 $O(N)$ 的暴力扫描，从白点集中找出距离当前整棵树面最近的点。总时间复杂度严格为 $O(N^2)$。当 $M$ 趋近于 $N^2$ 时，该算法由于没有优先队列的逻辑开销和堆调整的常数，运行效率极高。
方案乙：堆优化 Prim 算法（针对常规稠密图）
利用小根堆（优先队列）维护所有白点到当前树面的最小距离。每次出堆的操作为 $O(\log N)$，刷新周围点的边权代价为 $O(M \log N)$，总时间复杂度为 $O((N+M)\log N)$。
算法推导与状态设计
设计一个动态数组 $dist[i]$，其物理含义必须严格界定：表示未加入树的节点 $i$ 到当前已建立的生成树面 $S$ 的绝对最短距离。
注意：这与 Dijkstra 算法中 dist 表示“到源点的距离”有本质逻辑区别。
状态状态转移方程
设当前新并入树的蓝点为 $u$，对于所有与其直接相连的白点 $v \in (V-S)$：
$$dist[v] = \min(dist[v], w(u, v))$$
- 初始状态：任选一个源点（通常为 1 号点），令 $dist[1] = 0$，其余所有点 $dist[i] = \infty$。
- 熟化标记：使用布尔数组
vis[i]标定节点 $i$ 是否已并入蓝点集 $S$。
C++ 标准源码（两套工业级模板）
模板一：朴素 Prim 算法（$O(N^2)$ 极限稠密图神器）
#include <iostream>
#include <vector>
#include <algorithm>
const long long INF = 0x3f3f3f3f3f3f3f3fLL;
const int MAXN = 5005;
long long graph[MAXN][MAXN]; // 邻接矩阵存储稠密图
long long dist[MAXN]; // 存储白点到当前树面的最短距离
bool vis[MAXN]; // 标记是否已并入生成树 (蓝点集)
void prim_dense(int n) {
// 初始化物理边界
for (int i = 1; i <= n; ++i) {
dist[i] = INF;
vis[i] = false;
}
dist[1] = 0; // 自行选定 1 号点作为生成树的拓扑根节点
long long mst_weight = 0;
int node_count = 0;
for (int step = 1; step <= n; ++step) {
int u = -1;
long long min_d = INF;
// O(N) 暴力扫描，寻找距离当前树面最近的白点
for (int i = 1; i <= n; ++i) {
if (!vis[i] && dist[i] < min_d) {
min_d = dist[i];
u = i;
}
}
// 拓扑连通性校验：若找不到合法的点，说明图不连通
if (u == -1) {
std::cout << "orz\n";
return;
}
vis[u] = true; // 划归为蓝点
mst_weight += min_d;
node_count++;
// 用新加入的蓝点 u 刷新所有剩余白点到树面的距离
for (int v = 1; v <= n; ++v) {
if (!vis[v] && graph[u][v] < dist[v]) {
dist[v] = graph[u][v]; // 严格遵循：dist[v] = min(dist[v], w(u,v))
}
}
}
std::cout << mst_weight << "\n";
}模板二：堆优化 Prim 算法（$O(M \log N)$ 泛用型模板）
#include <iostream>
#include <vector>
#include <queue>
const long long INF = 0x3f3f3f3f3f3f3f3fLL;
const int MAXN = 100005;
struct Edge {
int to;
long long weight;
};
struct Node {
long long d;
int u;
bool operator>(const Node& rhs) const { return d > rhs.d; }
};
std::vector<Edge> adj[MAXN];
long long dist[MAXN];
bool vis[MAXN];
void prim_heap(int n) {
std::priority_queue<Node, std::vector<Node>, std::greater<Node> > pq;
for (int i = 1; i <= n; ++i) {
dist[i] = INF;
vis[i] = false;
}
dist[1] = 0;
pq.push(Node{0, 1});
long long mst_weight = 0;
int count = 0;
while (!pq.empty()) {
Node curr = pq.top();
pq.pop();
int u = curr.u;
if (vis[u]) continue; // 拦截堆内过期的脏数据
vis[u] = true;
mst_weight += curr.d;
count++;
for (size_t i = 0; i < adj[u].size(); ++i) {
int v = adj[u][i].to;
long long w = adj[u][i].weight;
if (!vis[v] && w < dist[v]) {
dist[v] = w;
pq.push(Node{dist[v], v}); // 将更优的边权及节点压入堆
}
}
}
if (count < n) std::cout << "orz\n";
else std::cout << mst_weight << "\n";
}NOIP 实战避坑指南
- 混淆 Prim 与 Dijkstra 的松弛方程：
这是初学者最高频的翻车点。Dijkstra 的松弛是基于路径累加的：
dist[u] + w < dist[v]。而 Prim 维护的是点到树面的距离，绝对不需要累加前驱权值，其方程严格为w < dist[v]。如果在 Prim 中错误地写成了 Dijkstra 的累加形式，求出的将是单源最短路树，而非最小生成树。 - 初始化未规避重边对邻接矩阵的破坏：
在使用朴素 Prim 算法（邻接矩阵）时，必须在读入边时执行重边拦截：
graph[u][v] = min(graph[u][v], w)。如果没有做min过滤，后续读入的较大重边会无情覆盖掉较小的有效边，导致整个最小生成树的代数基石被摧毁。
经典 NOIP/洛谷 真题
1. 洛谷 P1265 公路网络
- 题意描述： 给定平面上 $N$ 个城市的坐标。任意两个城市之间都可以修公路，建设成本等于它们之间的欧几里得距离。由于财政限制，修筑的公路网络必须使得任意两个城市可达，且总成本最小。此外，数据给出了特殊的限制：每个城市在连接时，必须优先选择物理距离最近的城市。求最小总成本。（$N \le 5000$）
- 问题本质与核心思路：
这道题是一道标准的平面完全图（稠密图）求 MST 问题。由于城市之间两两有边，边数 $M = \frac{N(N-1)}{2} \approx 1.25 \times 10^7$。
如果使用 Kruskal 算法，光是将所有边存下来就会导致内存开销巨大（MLE），更不用说对一千万条边排序引发的 TLE。
核心战术：选用朴素 Prim 算法。因为完全图的边权可以通过两点坐标在运行期动态计算（即
get_dist(i, j)），完全不需要显式建边存储邻接矩阵，空间复杂度成功降至 $O(N)$。利用外层循环推进，每次扫描未加入树的点，计算它们到当前树中各点的最小距离，在 $O(N^2)$ 的时空效率下优雅秒杀该题。
2. 洛谷 P2504 [HAOI2006] 聪明的猴子
- 题意描述： 在一片森林里有 $N$ 棵树，给出了每棵树的平面坐标。森林里有一群猴子，每只猴子的最大跳跃距离不同。如果两棵树之间的距离不超过猴子的最大跳跃距离，猴子就可以在这两棵树之间跳跃。猴子们想知道，有多少只猴子可以遍历所有的树。
- 问题本质与核心思路：
MST 最大边权瓶颈问题。
要让一只猴子能够遍历所有的树，这意味着由这些树构成的图网上，在猴子的跳跃距离限制下必须是连通的。根据生成树性质，要使整幅图连通，猴子的最小跳跃步长必须大于等于该图的最小生成树中的最大边权。
核心思路：利用点的坐标动态计算边权，通过 Prim 算法 求出这棵完全图的最小生成树。在 Prim 扩张的过程中，用一个变量
max_edge实时记录并更新并入生成树的 $N-1$ 条边中的最大边权。最后，遍历每只猴子的跳跃极限，只要其跳跃极限 $\ge \text{max\_edge}$，该猴子即可成功遍历，计数器加一。