[AcWing]858. Prim算法求最小生成树（C++实现）Prim算法模板题1. 题目2. 读题（需要重点注意的东西）3. 解法4. 可能有帮助的前置习题5. 所用到的数据结构与算法思想6. 总结

68 阅读 0 评论 45 点赞

我是靠谱客的博主忧心店员，最近开发中收集的这篇文章主要介绍[AcWing]858. Prim算法求最小生成树（C++实现）Prim算法模板题1. 题目2. 读题（需要重点注意的东西）3. 解法4. 可能有帮助的前置习题5. 所用到的数据结构与算法思想6. 总结，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

[AcWing]858. Prim算法求最小生成树（C++实现）Prim算法模板题

1. 题目
2. 读题（需要重点注意的东西）
3. 解法
4. 可能有帮助的前置习题
5. 所用到的数据结构与算法思想
6. 总结

1. 题目

在这里插入图片描述

2. 读题（需要重点注意的东西）

思路：
Prim算法的主要思想是：
1、首先先在图中任取一点加到最小生成树中；
2、遍历与这个最小生成树相连的所有边，取边权最小的且不成环的边和与这条边相连的节点加到最小生成树中；
3、重复步骤2，直到所有的节点都加到最小生成树中。
在这里插入图片描述
代码实现的主要流程：
1、首先任意加一个点到集合（最小生成树）内；
2、找到集合外到集合的距离（定义集合外到集合的距离为：集合外任意一点到集合内任意一点的距离的最小值）；
3、将这个点加到集合内，用找到的这个点更新其他点到集合的距离；
4、重复上述步骤，直到所有点加到集合内。

Prim算法主要是解决稠密图的最小生成树问题

3. 解法

---------------------------------------------------解法---------------------------------------------------

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

using namespace std;

const int N = 510, 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 ++ )
    {   
        int t = -1;
        // 找当前集合（最小生成树）外的距离最短的节点
        for (int j = 1; j <= n; j ++ )
            if (!st[j] && (t == -1 || dist[t] > dist[j]))
                t = j;
        // 如果找到的点到集合的最短距离是INF，则说明这是一个不连通的图，没有最小生成树
        if (i && dist[t] == INF) return INF;
        
        // 否则把这个点加到集合内
        if (i) 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()
{
    scanf("%d%d", &n, &m);

    memset(g, 0x3f, sizeof g);

    while (m -- )
    {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        g[a][b] = g[b][a] = min(g[a][b], c); // 建无向图，保留长度最小的那条边即可
    }

    int t = prim();

    if (t == INF) puts("impossible");// 有点不连通的时候，不存在最小生成树
    else printf("%dn", t);

    return 0;
}