Prim算法求最小生成树

思路

任取一个点当作初始集合，遍历集合外其他所有点找到一个距离该集合边权最近的点. 如果找到距离最近的点距离为无穷大，表示不存在最小生成树（不连通）返回INF，否则将该点加入集合重复以上操作即可，最后得到最小生成树的带权路径长度。

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;


// 0x3f3f3f3f十进制等于1061109567，数量级是10^9，而边长的最大情况为10^9
const int N = 510, M = 1e5 + 10, INF = 0x3f3f3f3f;

// 稠密图使用邻接矩阵来存储
int g[N][N];
int dist[N];        // 每个结点到集合的距离，初始化为无穷大
bool st[N];         // 标记每个结点是否已经被访问过
int n, m, res;

int prim()
{
    // 初始化所有的点的距离为无穷大
    memset(dist, 0x3f, sizeof dist);

    // 将第一个点加入集合，初始化距离为0
    dist[1] = 0;

    for (int i = 0; i < n; i ++ )
    {
        // 集合外距离集合最近的结点为t，遍历寻找该节点
        int t = -1;         // 初始化该结点为-1
        for (int j = 1; j <= n; j ++ )
            // 如果当前节点没有被访问过 并且 （当t为初始化值 或者 当前结点的距离比t结点的距离还要好）
            if (!st[j] && (t==-1 || dist[j] < dist[t]) )
                t = j;          // 更新当前的最短距离为t结点

        if (dist[t] == INF) return INF;     // 当前结点与集合不连通

        res += dist[t];         // 将最短距离添加到结果中
        st[t] = true;           // 标记当前节点已经被访问

        // 更新其他结点到集合的最短距离
        for (int j = 1; j <= n; j ++ )
        {
            dist[j] = min(dist[j], g[t][j]);
        }
    }
    return res;
}

int main()
{

    // 初始化集合中所有节点的距离为无穷大
    memset(g, 0x3f, sizeof g);

    scanf("%d%d", &n, &m);

    while (m -- )
    {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        // 无向图 每条边都要存储一遍
        g[a][b] = g[b][a] = min(g[a][b], c);
    }
    res = prim();
    if (res == INF) puts("impossible");
    else printf("%d", res);
    return 0;
}