GESP 8级 · 最小生成树-Prim

📖概念讲解

Prim算法是求最小生成树（MST）的经典贪心算法，属于图论中的核心考点。和Kruskal按边排序不同，Prim是从一个顶点出发，逐步扩展：每次从"已选集合"到"未选集合"的边中，挑一条最短的加入。

💡 核心区别：Kruskal是全局按边排序，适合稀疏图（边少）；Prim是局部贪心扩展，适合稠密图（边多）。复杂度用优先队列优化后为 O(E log V)。

易错点：Prim的 lowcost[i] 数组含义是"顶点 i 到已选集合的最短距离"，每次更新时只和新加入的顶点比较，而不是和所有已选顶点比较——因为之前已经是最优的了。

💻代码示例

#include<iostream>
#include<vector>
#include<climits>
using namespace std;
int prim(int n, vector<vector<int>>& g) {  // g[i][j]=边权, 不连通为0
    vector<int> lowcost(n, INT_MAX);  // lowcost[i]：顶点i到已选集合的最短距离
    vector<bool> inMST(n, false);     // 标记是否已加入生成树
    lowcost[0] = 0;                   // 从顶点0出发，初始距离为0
    int ans = 0;                       // MST总权值
    for (int i = 0; i < n; i++) {    // 每轮选一个顶点加入MST，共n轮
        int u = -1;                     // u = 本轮选中的顶点
        for (int j = 0; j < n; j++)   // 找距离最小且未入MST的顶点
            if (!inMST[j] && (u == -1 || lowcost[j] < lowcost[u]))
                u = j;
        inMST[u] = true;              // 将u加入MST
        ans += lowcost[u];              // 累加这条边的权值
        for (int j = 0; j < n; j++)   // 用u更新其他顶点的lowcost
            if (!inMST[j] && g[u][j] && g[u][j] < lowcost[j])
                lowcost[j] = g[u][j];   // 发现更短路径，更新
    }
    return ans;
}
int main() {
    int n = 4;                         // 4个顶点
    vector<vector<int>> g = {         // 邻接矩阵，0表示不连通
        {0, 2, 0, 5},                  // 顶点0到其他点的边
        {2, 0, 3, 0},                  // 顶点1到其他点的边
        {0, 3, 0, 1},                  // 顶点2到其他点的边
        {5, 0, 1, 0},                  // 顶点3到其他点的边
    };
    cout << "MST总权值: " << prim(n, g) << endl;
    return 0;
}
// 输出：MST总权值: 6

过程：0→1(2) → 1→2(3) → 2→3(1) = 2+3+1 = 6 ✅

🧩互动小测

Q1：Prim算法每次从所有未选顶点中选什么？

Q2：对于下面的图，Prim从顶点A出发，第一次选中加入MST的边是？
A-B:3, A-C:5, B-C:2, B-D:6, C-D:4

Q3：Prim和Kruskal分别更适合哪种图？

🏋️动手练一练

📝 编程练习

给定一个无向连通图的邻接矩阵，用Prim算法求最小生成树的总权值。

输入：第一行 n（顶点数，≤100），接下来 n×n 的矩阵，g[i][j] 表示 i 到 j 的边权（0表示无边，i==j时为0）。
输出：一个整数，最小生成树总权值。

提示：可以直接套用今天的模板，注意 lowcost 初始化为 INT_MAX，g[i][j]==0 表示无边。

参考答案：

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

int main() {
    int n; cin >> n;
    vector<vector<int>> g(n, vector<int>(n));
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            cin >> g[i][j];                  // 读入邻接矩阵

    vector<int> lowcost(n, INT_MAX);        // 到已选集合的距离
    vector<bool> inMST(n, false);           // 是否在MST中
    lowcost[0] = 0;
    int ans = 0;

    for (int i = 0; i < n; i++) {
        int u = -1;
        for (int j = 0; j < n; j++)         // 找最小lowcost
            if (!inMST[j] && (u == -1 || lowcost[j] < lowcost[u]))
                u = j;
        inMST[u] = true;
        ans += lowcost[u];
        for (int j = 0; j < n; j++)         // 用u更新
            if (!inMST[j] && g[u][j] && g[u][j] < lowcost[j])
                lowcost[j] = g[u][j];
    }
    cout << ans << endl;
    return 0;
}

要点：核心就是 lowcost 数组的含义——记录每个未选顶点到已选集合的最短距离，每次加入新顶点后用它更新其他顶点的 lowcost 即可。

📝易错点提醒

🔴 lowcost[0]=0 的含义：不是"0到0的距离是0"，而是让顶点0第一个被选中（距离最小的优先出队）。
🔴 g[u][j]==0 不是权值0：邻接矩阵中 0 表示"无边"，权值为0的边要特殊处理或用一个较大的值替代。
🔴 更新时只和u比较：lowcost[j] = min(lowcost[j], g[u][j])，不要遍历所有已选顶点，那样就退化成O(n³)了。
🔴 图不连通时：如果某轮找不到 lowcost < INT_MAX 的顶点，说明图不连通，MST不存在——记得特判。

📘最小生成树 — Prim算法

📖概念讲解

💻代码示例

🧩互动小测

Q1：Prim算法每次从所有未选顶点中选什么？

Q2：对于下面的图，Prim从顶点A出发，第一次选中加入MST的边是？A-B:3, A-C:5, B-C:2, B-D:6, C-D:4

Q3：Prim和Kruskal分别更适合哪种图？

🏋️动手练一练

📝 编程练习

📝易错点提醒

Q2：对于下面的图，Prim从顶点A出发，第一次选中加入MST的边是？
A-B:3, A-C:5, B-C:2, B-D:6, C-D:4