同样是求最小生成树，换一个角度：不给边排序，而是从一个点出发，像树在生长一样，每次贪心地吞并离自己最近的那个新点。
15.4 节的 Kruskal 站在"边"的视角：把所有边排好序，一条条考察要不要加入。Prim 算法站在"点"的视角：从某一个点开始，维护一棵正在生长的树，每一步都贪心地选一条连接"树内"和"树外"、权值最小的边，把树外的那个点纳入树中——像细胞分裂一样，树每一步只长大一个点，直到把所有点都纳入进来。
这个"每次贪心地吞并最近的新点"的过程，和 15.3 节 Dijkstra 的操作方式几乎一模一样——区别只在于贪心的依据：Dijkstra 比较的是"离起点的累计距离"，Prim 比较的是"离当前树最近的单条边权值"。
| 步骤 | 做什么 |
|---|---|
| ① 初始化 | 随便挑一个起点纳入树中，其余点都在树外 |
| ② 找候选边 | 在所有"一端在树内、一端在树外"的边里，找权值最小的那一条 |
| ③ 扩展 | 把这条边和它树外的那个端点，一起纳入树中 |
| ④ 重复 | 重复 ②③，直到所有点都被纳入树中（选够 V-1 条边） |
还是 15.1～15.4 节的示例图（A-B=4，A-C=1，B-C=2，B-D=5，C-D=8），从 A 出发跑一遍 Prim：
| 当前树 | 树内→树外的候选边 | 选中最小的一条 | 树扩展为 |
|---|---|---|---|
| {A} | A-B(4)，A-C(1) | A-C(1) | {A, C} |
| {A, C} | A-B(4)，C-B(2)，C-D(8) | C-B(2) | {A, B, C} |
| {A, B, C} | B-D(5)，C-D(8) | B-D(5) | {A, B, C, D} |
A-C(1)、B-C(2)、B-D(5)，总权值 1+2+5=8——和 15.4 节 Kruskal 算出的结果完全一样（这并非巧合：只要图连通，最小生成树的总权值是唯一确定的，Kruskal、Prim 只是用不同顺序把它找出来）。留意第二步：A-B(4) 一直摆在候选里，但因为后来出现了更便宜的 C-B(2)，它从未被选中——这也是"贪心"在每一步都做局部最优选择的体现。| 1 | const int INF = 0x3f3f3f3f; |
| 2 | vector<pair<int,int>> adj[MAXN]; // adj[u]：(邻居, 边权) |
| 3 | int key_[MAXN]; // key_[v]：目前"树到 v"最便宜的单条边权值 |
| 4 | bool inTree[MAXN]; // v 是否已经被纳入树中 |
| 5 | |
| 6 | int Prim(int n) // 从 1 号点出发，返回最小生成树总权值（不连通返回 -1） |
| 7 | { |
| 8 | fill(key_ + 1, key_ + 1 + n, INF); |
| 9 | priority_queue<pair<int,int>, vector<pair<int,int>>, greater<>> pq; |
| 10 | key_[1] = 0; pq.push({0, 1}); // 起点距离"树"的代价记为 0 |
| 11 | |
| 12 | int total = 0, cnt = 0; |
| 13 | while (!pq.empty()) |
| 14 | { |
| 15 | auto [d, u] = pq.top(); pq.pop(); |
| 16 | if (inTree[u]) continue; // ★ u 已经在树里了，这条是过时记录，跳过 |
| 17 | inTree[u] = true; |
| 18 | total += d; cnt++; // 把"吞并 u 花的这条边权值"计入总权值 |
| 19 | |
| 20 | for (auto [v, w] : adj[u]) |
| 21 | { |
| 22 | if (!inTree[v] && w < key_[v]) // v 还在树外，且这条边比 v 已知最便宜的边还便宜 |
| 23 | { |
| 24 | key_[v] = w; |
| 25 | pq.push({w, v}); |
| 26 | } |
| 27 | } |
| 28 | } |
| 29 | return cnt == n ? total : -1; |
| 30 | } |
w < key_[v]——只看这一条边本身的权值；而 15.3 节 Dijkstra 第 18 行判断的是 dist_[u] + w < dist_[v]——看的是累计距离。这正是 ① 提到的"单条边权值"和"累计距离"的区别，也是 Prim 和 Dijkstra 唯一的本质差异。另外这里用了显式的 inTree[] 数组（而不是 15.3 节 Dijkstra 那种"比较 d 和 dist_[u]"的过时判断），两种写法都能达到同样的"跳过重复处理"效果，属于同一个技巧的不同实现方式。| 对比项 | Kruskal（15.4 节） | Prim（本节） |
|---|---|---|
| 贪心视角 | 边——排序后逐条考察 | 点——树逐步扩展 |
| 依赖的数据结构 | 并查集 | 优先队列（或邻接矩阵朴素实现） |
| 时间复杂度 | O(E log E)，只和边数有关 | 堆优化 O(E log V)；邻接矩阵朴素版 O(V²)，只和点数有关 |
| 适合场景 | 稀疏图（边数远小于 V²） | 稠密图（边数接近 V²）用朴素版更快 |
w < key_[v]（只看这条边本身），如果照抄 Dijkstra 写成 key_[u] + w < key_[v]，算出来的就不再是最小生成树，而是变成了一个和 Dijkstra 功能重复、意义不明的东西。cnt 会小于 n。第 29 行用 cnt == n 判断这种情况，返回 -1 表示生成树不存在。V²），堆里会塞进大量边，O(E log V) 里的 E 趋近 V²，反而不如"不用堆，每轮直接 O(V) 线性扫描找最小候选点"的朴素版 O(V²) 实现划算——这是稠密图场景下值得注意的优化方向。