一、算法概述

Prim 算法是一种用于求解加权无向连通图的最小生成树（MST） 的贪心算法。它从一个顶点开始，逐步扩展生成树，每次选择连接已选顶点集和未选顶点集的最小权重边。

二、算法思想

1. 初始化：从任意顶点开始，将其加入生成树集合

2. 重复执行：

• 在所有连接已选顶点和未选顶点的边中，选择权重最小的边

• 将该边加入生成树，并将对应的未选顶点加入已选集合

3. 终止条件：当所有顶点都加入生成树时结束

三、算法过程示例

示例图（顶点：A,B,C,D；边权重如图）：

更清晰的邻接关系（无向图，权重如图）：

• A–B : 2

• A–C : 4

• A–D : 3

• B–D : 1

• C–D : 5

顶点集合：{A, B, C, D}
目标：用 Prim 算法找最小生成树（MST）。

每次选择连接 已选顶点集 与 未选顶点集 的最小权重边，将该边及其另一端点加入已选集合。

步骤 1

• 已选集合 $S=\{A\}$

• 候选边（一端在 S，一端不在 S）：

• A–B (2)   （说明:A在S中，B不在S中）

• A–C (4)   （说明:A在S中，C不在S中）

• A–D (3)   （说明:A在S中，D不在S中）

• 最小权重边：A–B (2)

• 加入 B 到 S，边 A–B 加入 MST。

MST 边：{A–B}
S = {A, B}

步骤 2

• S = {A, B}

• 候选边（一端在 S，一端不在 S）：

• A–C (4) （说明:A在S中，C不在S中）

• A–D (3) （说明:A在S中，D不在S中）

• B–D (1)  （说明:B在S中，D不在S中）

• 最小权重边：B–D (1)

• 加入 D 到 S，边 B–D 加入 MST。

MST 边：{A–B, B–D}
S = {A, B, D}

步骤 3

• S = {A, B, D}

• 候选边（一端在 S，一端不在 S）：

• A–C (4)    （说明:A在S中，C不在S中）

• A–D (3)   （说明:A在S中，D在S中,不能选，会形成环）

• C–D (5)     （说出：C不在S中，D在S中）

• 有效候选边（另一端不在 S）：

• A–C (4)

• C–D (5)

• 最小权重边：A–C (4)

• 加入 C 到 S，边 A–C 加入 MST。

MST 边：{A–B, B–D, A–C}
S = {A, B, D, C}（已包含所有顶点）

步骤 4

所有顶点已在 S，算法结束。

MST 总权重=2+4+1=7

四、为什么是对的

Prim 算法的正确性基于 MST 的割性质（Cut Property）：

对于图的任意一个割（把顶点分成两个集合 S 和 V−S），连接这两个集合的最小权重边一定属于某个最小生成树。

算法过程解释：

1. 初始时，S 只有一个顶点，割是 S 与 V−S。

2. 每次选连接 S 与 V−S 的最小权重边 e，根据割性质，这条边一定在某个 MST 中。

3. 将 e 加入 MST，并把 e 在 V−S 中的那个顶点加入 S。

4. 重复直到 S=V，此时所有加入的边构成一棵树，且每一步都符合 MST 的边，因此最终得到的就是 MST。

可以把上面的性质换成下面的例子？

想象有 4 个岛屿（A、B、C、D），它们之间可以造桥，但造桥的成本不同。
我们想用最低总成本造桥，让所有岛屿连通（可以互相到达），并且不造多余的桥（避免环）。

Prim 算法的思路

1. 随便选一个岛作为起点（比如 A）。

• 现在“已连通区” = {A}，其他岛是“未连通区”。

2. 从已连通区 造桥到 未连通区，选最便宜的那座桥。

• 为什么必须这样选？
  因为最终所有岛都要连通，迟早要造一座桥从已连通区通往某个未连通岛。
  如果现在不选最便宜的，以后还是要造桥过去，但那时可能更贵，总成本就高了。
  所以现在选最便宜的桥不会错。

3. 桥造好后，那个新岛就加入“已连通区”。

• 重复第 2 步，直到所有岛都连通。

五、参考代码

1. 朴素解法 （临接矩阵）
   

#include <iostream>
#include <climits>
using namespace std;
const int V = 5;  // 图的顶点数量（可按需修改，有类型检查，更安全）
// 函数功能：找到未加入最小生成树(MST)且权重最小的顶点
//   key[]: 数组，存储每个顶点到当前生成树的最小权重值
//   mstSet[]: 布尔数组，标记顶点是否已加入最小生成树（true=已加入，false=未加入）
// 返回值：返回未加入MST且权重最小的顶点的索引
int minKey(int key[], bool mstSet[]) {
    // 初始化最小值为无穷大，最小顶点索引暂未确定
    int min = INT_MAX, min_index;
    // 遍历所有顶点，寻找符合条件的最小权重顶点
    for (int v = 0; v < V; v++) {
        // 条件1：顶点v未加入MST（mstSet[v]为false）
        // 条件2：顶点v的当前最小权重小于当前记录的最小值
        if (!mstSet[v] && key[v] < min) {
            min = key[v];       // 更新最小值为当前顶点的权重
            min_index = v;      // 记录最小权重顶点的索引
        }
    }
    return min_index;  // 返回找到的最小权重顶点索引
}
// 函数功能：打印最小生成树的边、对应权重，以及总权重
//   parent[]: 数组，存储每个顶点在生成树中的父节点（用于确定边的两个端点）
//   graph[V][V]: 存储图的邻接矩阵，graph[i][j]表示顶点i到j的边权重（0表示无边）
void printMST(int parent[], int graph[V][V]) {
    // 输出表头，\t表示制表符，让格式更整齐
    cout << "边 \t权重\n";
    int totalWeight = 0;  // 定义变量，累加生成树的总权重
    // 遍历第1到第V-1个顶点（第0个顶点是根节点，无父节点，无需遍历）
    for (int i = 1; i < V; i++) {
        // 输出：父节点 - 当前节点  对应的边权重
        cout << parent[i] << " - " << i << " \t" << graph[i][parent[i]] << "\n";
        // 累加每条边的权重到总权重
        totalWeight += graph[i][parent[i]];
    }
    // 输出生成树的总权重
    cout << "总权重: " << totalWeight << endl;
}

// 函数功能：Prim算法核心实现（邻接矩阵版），构建最小生成树
// 参数说明：graph[V][V] 输入的图的邻接矩阵，无向图满足graph[i][j] = graph[j][i]
void primMST(int graph[V][V]) {
    int parent[V];      // 存储最小生成树的结构：parent[i]表示顶点i在MST中的父节点
    int key[V];         // 键值数组：key[i]表示顶点i到当前MST的最小权重边的权重值
    bool mstSet[V];     // 标记数组：mstSet[i]=true 表示顶点i已加入MST
    
    // 初始化：所有顶点的key值设为无穷大（表示初始时到MST无连接），且都未加入MST
    for (int i = 0; i < V; i++) {
        key[i] = INT_MAX;   // 无穷大表示暂时没有到MST的边
        mstSet[i] = false;  // 初始状态所有顶点都不在MST中
    }
    
    // 选择第0个顶点作为MST的起点（根节点）
    key[0] = 0;         // 起点到自身的权重为0（无成本）
    parent[0] = -1;     // 根节点没有父节点，用-1标记
    
    // MST有V个顶点，需要V-1条边，因此循环V-1次来选择边
    for (int count = 0; count < V - 1; count++) {
        // 步骤1：找到未加入MST且key值最小的顶点u
        int u = minKey(key, mstSet);
        // 步骤2：将顶点u加入MST
        mstSet[u] = true;
        
        // 步骤3：更新顶点u的所有相邻顶点的key值和父节点
        for (int v = 0; v < V; v++) {
            // 条件说明：
            // 1. graph[u][v] != 0：顶点u和v之间有边相连（邻接矩阵中0表示无边）
            // 2. !mstSet[v]：顶点v未加入MST
            // 3. graph[u][v] < key[v]：u-v这条边的权重比v当前的最小权重更小
            if (graph[u][v] && !mstSet[v] && graph[u][v] < key[v]) {
                parent[v] = u;          // 更新v的父节点为u
                key[v] = graph[u][v];   // 更新v到MST的最小权重为u-v边的权重
            }
        }
    }
    // 打印最终生成的最小生成树
    printMST(parent, graph);
}

int main() {
    // graph[i][j] = w 表示顶点i到j有一条权重为w的无向边；0表示i和j之间无边
    // 例如：graph[0][1]=2 表示顶点0和1之间有一条权重为2的边
    int graph[V][V] = {
        {0, 2, 0, 6, 0},  // 顶点0的邻边：0-1(权重2)、0-3(权重6)，其余无边
        {2, 0, 3, 8, 5},  // 顶点1的邻边：1-0(2)、1-2(3)、1-3(8)、1-4(5)
        {0, 3, 0, 0, 7},  // 顶点2的邻边：2-1(3)、2-4(7)，其余无边
        {6, 8, 0, 0, 9},  // 顶点3的邻边：3-0(6)、3-1(8)、3-4(9)，其余无边
        {0, 5, 7, 9, 0}   // 顶点4的邻边：4-1(5)、4-2(7)、4-3(9)，其余无边
    };
    // 输出提示信息
    cout << "Prim算法生成的最小生成树:\n";
    // 调用Prim算法函数，生成并打印最小生成树
    primMST(graph);
    return 0;
}

2.优先队列解法

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

// pii 表示 (边权重, 顶点编号) 的键值对，
typedef pair<int, int> pii;  

// 全局变量：存储图的核心信息（替代原Graph类的成员变量）
int V;                      // 图的顶点总数
vector<vector<pii>> adj;    // 邻接表：adj[u] 存储 (相邻顶点v, 边权重w) 的列表

// 初始化图
// n表示图的顶点总数
void initGraph(int n) {
    V = n;
    adj.resize(V);  // 初始化邻接表大小为顶点数
}
// 添加无向边
//   u: 起点编号
//   v: 终点编号
//   w: 边的权重
void addEdge(int u, int v, int w) {
    adj[u].push_back({v, w});  // 向u的邻接表添加v和权重w
    adj[v].push_back({u, w});  // 无向图：v的邻接表也要添加u和权重w
}

// 优先队列（最小堆）优化的Prim算法，构建最小生成树(MST)
void primMST() {
    // 优先队列（最小堆）：存储 (权重, 顶点)，堆顶始终是权重最小的元素
    // greater<pii> 表示按权重升序排列，实现最小堆（默认是最大堆）
    priority_queue<pii, vector<pii>, greater<pii>> pq;
    
    vector<int> key(V, INT_MAX);      // key[v]：顶点v到当前MST的最小权重，初始为无穷大
    vector<int> parent(V, -1);        // parent[v]：顶点v在MST中的父节点，初始为-1（无父节点）
    vector<bool> inMST(V, false);     // inMST[v]：标记顶点v是否已加入MST，初始为false
    
    // 选择顶点0作为MST的起点
    pq.push({0, 0});  // 起点权重为0，加入优先队列
    key[0] = 0;       // 起点到自身的权重设为0

    // 遍历优先队列，直到所有顶点加入MST
    while (!pq.empty()) {
        // 步骤1：取出堆顶元素（权重最小的顶点）
        int u = pq.top().second;  // 获取顶点编号（second是顶点，first是权重）
        pq.pop();                // 弹出堆顶
        
        // 跳过已加入MST的顶点（避免重复处理）
        if (inMST[u]) continue;
        inMST[u] = true;         // 将顶点u标记为已加入MST
        
        // 步骤2：遍历顶点u的所有相邻顶点，更新权重
        for (auto &neighbor : adj[u]) {
            int v = neighbor.first;    // 相邻顶点编号
            int weight = neighbor.second;  // u-v边的权重
            
            // 条件：v未加入MST 且 u-v边的权重 < v当前的最小权重
            if (!inMST[v] && key[v] > weight) {
                key[v] = weight;       // 更新v到MST的最小权重
                pq.push({key[v], v});  // 将新的权重和顶点加入优先队列
                parent[v] = u;         // 更新v的父节点为u
            }
        }
    }
    
    // 步骤3：打印MST的边、权重和总权重
    cout << "边 \t权重\n";
    int totalWeight = 0;  // 存储MST的总权重
    // 遍历1~V-1顶点（0是根节点，无父节点）
    for (int i = 1; i < V; i++) {
        cout << parent[i] << " - " << i << " \t" << key[i] << "\n";
        totalWeight += key[i];  // 累加每条边的权重
    }
    cout << "总权重: " << totalWeight << endl;
}

int main() {
    // 初始化图：5个顶点的无向带权图（替代原Graph g(5)）
    initGraph(5);
    
    // 依次添加边（起点, 终点, 权重）
    addEdge(0, 1, 2);
    addEdge(0, 3, 6);
    addEdge(1, 2, 3);
    addEdge(1, 3, 8);
    addEdge(1, 4, 5);
    addEdge(2, 4, 7);
    addEdge(3, 4, 9);
    
    // 输出提示信息并调用Prim算法
    cout << "Prim算法（优先队列优化）生成的最小生成树:\n";
    primMST();
    
    return 0;
}