详解 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; // 将当轮要加入的点初始化为-1
        for (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;
}