详解 Prim 算法的实现

一、算法思路

Prim 算法是用来求最小生成树的，它的思想也有点类似于贪心——逐个将离当前集合最近的点加入到集合中，直至发现图不连通或所有点都被加到集合中，算法即宣告终止。它的具体做法是：

• step 1：初始时，由当前最小生成树中的点构成的集合 $S$ 为空，图中剩余的点到集合的距离皆为 $+\infty$，这一步可以用代码实现如下：

  // 假定图中共有N个点
  bool st[N]; // 用bool数组st来模拟集合S，若一个点i被加入集合，// 则将st[i]置为true
  int dist[N]; // 用dist数组来记录所有点到当前集合的最短距离，
  memset(dist, 0x3f, sizeof dist); // 初始时，将所有点到集合的最短// 距离置为正无穷
  

• step 2：接下来是 n 轮循环，每轮循环的任务是找到当前离集合最近的点并将其加入集合（即合并到当前的最小生成树上），同时，用这个点更新其他点到集合的距离（当这个点加入集合后，其他点到集合的最短距离有可能发生改变，因为此时这个新加入的点也是集合的一部分了，所以要用这个点到其他点的距离来更新其他点到集合的最短距离），这一步的代码可以实现如下：

  // n是图中所有点的个数
  for (int i = 0; i < n; i++) // n轮循环，每轮循环负责将一个点加入集合中
  {// 首先要找到我们要加入的点是谁int t = -1; // 先用-1来暂时表示这个点，并用t来记录// 执行具体的寻找过程：从1~n这n个点中将当前这一轮的t找出来for (int j = 1; j <= n; j++) // 从1到n循环n个点，看哪个点符合要求if (!st[t] && (t == -1 || dist[j] < dist[t])) // 如果这个点尚未在集合中，并且// 要么找到了第一个不在集合中的点，// 要么找到了离集合最短距离更小的点t = j; // 就更新t的取值// 当我们找到t以后，我们需要将t加入到集合中，st[t] = true;// 并用t到其他点的距离更新其他点到集合的最短距离for (int j = 1; j <= n; j++)dist[j] = min(dist[j], g[t][j]);
  }
  

• step 3：如何返回最终的结果呢？我们要找的是我们要返回的是最小生成树的树边权重之和（以下简记为“最小生成树的长度”），而这个长度是由一条条边加起来得到的。注意到，每次往集合中新加入一个点，就相当于当前最小生成树又多了一条边，而这条边就是我们要找的众多边之一。因此，只需要在每次新加入一条边的时候，把新加入的边的长度累加到最终的结果中去即可（这个长度即为新加入的点到集合的最短距离，即为 dist[t]）。
  然而如果图中根本就不存在最小生成树怎么办呢？如果在中途就发现了图中必然不可能存在最小生成树，那能不能提前停止并返回结果呢？如果可以，当如何实现呢？
  答案是我们可以在加入每个点之前先做一个判断：如果新加入的点到集合的最短距离是 $+\infty$ ，这就意味着新加入的点跟集合中的点根本就不连通，此时图中必不可能存在最小生成树，而一旦我们发现了这样一种情况，就可以提前退出循环，并将当前结果报告出去，其实现代码如下：

  // 用res来记录最终最小生成树的长度
  int res = 0; // 初始时res为0
  for (int i = 0; i < n; i++) // 最外层的n轮循环，每轮找到一个点并加入当前集合中
  {int t = -1;for (int j = 1; j <= n; j++)if (!st[j] && (t == -1 || dist[j] < dist[t]))t = j;// 找到t以后，这个t不一定是与当前集合连通的，所以可以提前做一个判断：if (i && dist[t] == INF) return INF; // 如果当前点到集合的最短距离为正无穷，则返回正无穷（最终可根据返回结果是否为正无穷来判断图中是否存在最小生成树）// 如果上一步没有提前返回，则说明当前点与集合是连通的，那么它与集合之间将会连起一条新的边，这个边是最终最小生成树的一部分，要将它累加至最后的结果中：if (i) res += dist[t];// 注意以上两步中都有一个if(i)，这个判断的目的是：i=0表示第一轮循环（即将第一个点加入最小生成树），由于第一个点到初始空集合S的距离为正无穷，所以这个点不能作为“不存在最小生成树”的判断，这个点到集合的距离也不能累加至最终的结果中，因此正确的做法是跳过这个点，即加一个if(i)的判断...// 最终返回res即可return res;
  }
  

二、Prim 算法求最小生成树的完整代码如下：

#include <iostream>
#include <cstring>using namespace std;const int N = 510, M = 2e5 + 10; // 边数设为初始值的两倍，是因为无向图要加两条有向边
const int INF = 0x3f3f3f3f;int n, m;
int g[N][N];
int dist[N];
bool st[N];int prim()
{memset(dist, 0x3f, sizeof dist); // 初始时，设置所有点到集合的最短距离都为正无穷int res = 0; // 用res记录最终最小生成树的长度for (int i = 0; i < n; i++) // 然后开始n轮循环，每轮将一个点加入当前集合中{int t = -1; // 将当轮要加入的点初始化为-1for (int j = 1; j <= n; j++) // 然后从1~n这n个点中找到当前这一轮要加入的点if (!st[j] && (t == -1 || dist[j] < dist[t]))t = j;// 找到以后，先做判断，看图会不会不连通if (i && dist[t] == INF) return INF;// 如果确认当前这一轮还未发现图是不是不连通的，就先将当前边累加至最终结果if (i) res += dist[t];// 关键一步：用t到它所有邻居的距离更新它的所有邻居到当前集合的最短距离for (int j = 1; j <= n; j++) // 遍历并找到t的所有邻居dist[j] = min(dist[j], g[t][j]); // 更新邻居到当前集合的距离// 最后，将当前这个点t加入到当前集合中st[t] = true;}return res; // 返回图中最小生成树的长度
}int main()
{cin >> n >> m;memset(g, 0x3f, sizeof g); // 初始时，设置所有边权都为正无穷// 这一步是不可省略的，因为有些点之间根本就没有连接，其距离为正无穷，// 如果不进行这一步设置，这些不连通的点之间的边将被默认初始化为0，// 这显然是不对的while (m--){int a, b, w;scanf("%d%d%d", &a, &b, &w);g[a][b] = g[b][a] = min(g[a][b], w);}int res = prim();if (res == INF) puts("impossible");else cout << res << endl;return 0;
}

【注】以上内容参考AcWing。