一、算法概述

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;  }