GESP 8级 · 最小生成树

Prim 算法是另一种求最小生成树的方法。和 Kruskal 从"边"的角度出发不同，Prim 从"顶点"出发——从一个起点开始，每次找到连接"已选区域"和"未选区域"的最短边，把它纳入，直到所有顶点都被选中。

💡 这是什么？

生活比喻：想象你在装修房子。你从客厅开始（起点），然后找"从已装修区域到未装修区域"的最便宜的工序来执行。比如先装完客厅，然后发现铺客厅到卧室的地板最便宜，就铺它。接着发现刷卧室的墙最便宜，就刷它……不断扩展已装修区域，直到整栋房子都装修好。

与 Kruskal 的区别：
• Kruskal：站在全局，把所有边排序，一条一条挑（不管两端在哪）
• Prim：站在某个起点，逐步向外"扩张"，像病毒扩散一样

两种算法得到的 MST 权值一定相同（最小生成树的总权值是唯一的），但选出的边可能不同。

🌟 为什么重要？

• 和 Kruskal 互补：稠密图（边很多）时 Prim 比 Kruskal 更快
• 思路类似 Dijkstra：如果你已经学过 Dijkstra 最短路，Prim 几乎是一样的模板
• GESP 8级必考：两种 MST 算法都会考，经常对比考查
• 实际应用：电线布线、管道铺设等"从一点扩展"的场景很自然

📋 前置知识（学这个之前你需要知道）

1. 图的基本概念（GESP 3-4级）：邻接表、无向图、边权
2. 优先队列 / 堆（GESP 5级）：priority_queue，用于每次快速找最小边
3. Dijkstra 最短路算法：Prim 的代码结构和 Dijkstra 几乎一样，建议先学 Dijkstra
4. 贪心思想：每一步都选当前最优的连接方式

如果你已经会 Dijkstra，那 Prim 基本上换个思路就懂了！

📐 Prim 算法步骤

① 任选一个起点（比如节点 0），加入"已选集合"
② 维护 lowcost[i] = 节点 i 到"已选集合"的最短距离
   初始：lowcost[起点]=0，其余=∞
③ 每次从优先队列中取距离最小的未选节点 u
   → 将 u 加入已选集合，mst += lowcost[u]
④ 用 u 的所有邻居 v 更新 lowcost[v]
   如果 w(u,v) < lowcost[v]，更新并入队
⑤ 重复③④，直到选了 n 个节点

💻 完整代码（带详细注释）

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

const int N = 100010;
const int INF = 0x3f3f3f3f;

vector<pair<int,int>> adj[N]; // 邻接表：adj[u] = {(v, w), ...} 表示 u 到 v 权重 w

// Prim 主算法：从节点0出发求最小生成树
int prim(int n) {
    // lowcost[i] = 节点 i 到"已选集合"的最短距离
    vector<int> lowcost(n, INF);
    // visited[i] = 节点 i 是否已被选入 MST
    vector<bool> visited(n, false);

    // 从节点 0 出发
    lowcost[0] = 0;  // 起点到自己的距离是 0

    // 优先队列：(距离, 节点编号)，小的优先
    priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> pq;
    pq.push({0, 0});  // 把起点入队

    int mstWeight = 0;  // MST 总权值
    int count = 0;      // 已选节点数

    while (!pq.empty()) {
        // 取出距离最小的节点
        auto [dist, u] = pq.top();  // dist=距离, u=节点编号
        pq.pop();

        // 如果这个节点已经被选过了，跳过（类似 Dijkstra 的松弛判断）
        if (visited[u]) continue;
        visited[u] = true;  // 标记为已选
        mstWeight += dist;  // 累加边权
        count++;            // 已选节点数+1

        // 用 u 去更新它的所有邻居
        for (auto& [v, w] : adj[u]) {  // v=邻居, w=u到v的边权
            if (!visited[v] && w < lowcost[v]) {
                // 发现一条更短的路径到达 v
                lowcost[v] = w;       // 更新最短距离
                pq.push({w, v});      // 入队
            }
        }
    }

    // 如果选了 n 个节点，说明图连通，返回 MST 权值
    // 如果 count < n，说明图不连通，没有生成树
    if (count == n) return mstWeight;
    return -1;  // 图不连通
}

int main() {
    int n, m;  // n 个顶点，m 条边
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        adj[u].push_back({v, w});  // 无向图，双向都要加
        adj[v].push_back({u, w});
    }
    cout << prim(n) << endl;
    return 0;
}

🔍 算法执行过程举例

假设有4个城市，从节点0出发：
边: (0,1,1) (0,2,3) (1,2,2) (2,3,4)

初始：lowcost = [0, ∞, ∞, ∞]，入队 (0,0)
第1轮：取出(0,0)，visited[0]=true
   邻居1：lowcost[1] = min(∞, 1) = 1 → 入队(1,1)
   邻居2：lowcost[2] = min(∞, 3) = 3 → 入队(3,2)
   mstWeight = 0, count = 1
第2轮：取出(1,1)，visited[1]=true
   邻居0：已访问，跳过
   邻居2：lowcost[2] = min(3, 2) = 2 → 入队(2,2)
   mstWeight = 0+1=1, count = 2
第3轮：取出(2,2)，visited[2]=true
   邻居3：lowcost[3] = min(∞, 4) = 4 → 入队(4,3)
   mstWeight = 1+2=3, count = 3
第4轮：取出(4,3)，visited[3]=true
   mstWeight = 3+4=7, count = 4
结果：MST权值 = 7（和 Kruskal 一样！）

⏱ 复杂度分析

邻接表 + 优先队列：O(m log m)，m 是边数
邻接矩阵 + 普通数组：O(n²)，适合稠密图

选择建议：
• 稀疏图（m 远小于 n²）→ 用 Kruskal 或 Prim 优先队列版
• 稠密图（m 接近 n²）→ 用 Prim 邻接矩阵版更简单

⚠️ 易错点

1. 忘记跳过已访问节点 → if (visited[u]) continue; 这行不能漏，否则会重复累加边权。
2. lowcost 初始值 → 除了起点设为0，其他都要设为 INF（很大的数），不能设为0。
3. 无向图要加双向边 → adj[u].push_back({v,w}) 和 adj[v].push_back({u,w}) 都要写。
4. 忘记判不连通 → 如果最后 count < n，说明图不连通，此时没有 MST。
5. 优先队列存的是旧值 → 同一个节点可能在队列中出现多次（不同距离），靠 visited 数组去重。

🎯 练习建议

入门练习：
• 洛谷 P3366 【模板】最小生成树（先用 Kruskal 做，再用 Prim 做，对比结果）

进阶练习：
• 洛谷 P4047 [JSOI2010]部落（Prim/Kruskal 灵活运用）
• 洛谷 P1661 扩散（建模题）

学习方法：
① 如果你会 Dijkstra，直接把 Dijkstra 的 dist 换成 lowcost，目标从"到起点最短"换成"到已选集合最短"即可
② 对比 Kruskal 和 Prim 的代码，理解两种完全不同的思路
③ 注意：两种方法得到的 MST 总权值一定相同，但具体边可能不同

← 上一个：最小生成树 · Kruskal 📖 返回主目录下一个：拓扑排序 →

最小生成树 · Prim