历史记录

清除记录

猜你想搜

AcWing热点
App
登录/注册

cht讲算法——prim算法

作者：

cht , 2020-07-11 21:12:44 , 所有人可见 , 阅读 931

9

3

prim算法

提前说一句，prim能生成迷宫，效果很不错，比Astar强多了。

~~（这应该是ta唯一能赢过克鲁斯卡尔算法的地方。~~

最小生成树的概念。

这里先给大家推荐一篇好文。
最小生成树理论基础
我这里再讲一下什么是最小生成树。
我们这里举一个y总举过的栗子。
y总：

最小生成树问题有很多实际应用。
比如我们修公路，有n条可以修的，要求必须连接所有点，
但我们不能花太多钱，这就是一个最小生成树问题。

prim算法的步骤

其实这个算法挺抄袭的。
抄袭的是DIJkstra。
为啥呢？
大家对比一下算法步骤。
prim算法是首先进行代谢。
每次代谢，首先找出距离已经更新的集合的最短的边。
然后跟Dijkstra一样，
把这个点放进集合
然后用集合更新这个点……

我们类比一下Dijkstra的思路。

一、找到目前不在st中距离最近的点。
二，把这个点放进st集合。
三、用之前的点更新这个点。

这……
好了不管版权的问题（猫猫吃瓜，不嫌事大）。
我们继续。

prim算法的代码与板子

朴素prim算法一般用邻接矩阵存。
另外还需要dist数组来存距离集合的距离。
st数组判重。

首先处理一下dist数组，初始化为`0x3f`。

memset(dist, 0x3f, sizeof dist);

注意我们一般是去求最小生成树的边权之和。
所以用res来存。

int res = 0;

然后迭代一遍所有边，这个没啥好说的，循环。

for(int i = 0; i < n; i ++)
{

}

然后接下来找距离集合最近的点和Dijkstra差不多（还是完全一样？

int t = -1;
for(int j = 1; j <= n; j ++)
    if(!st[j] && (t == -1 || dist[t] > dist[j]))
        t = j;

我们对比一下Dijkstra的板子。

int t = -1;
for(int j = 1; j <= n; j ++)
    if(!st[j] && (t == -1 || dist[t] > dist[j]))
        t = j;

这……

好了不水了。

判断不存在最小生成树

一想就立刻知道如果即将更新的点啥都不是直接pass。
不过考虑边界，i不能为0。

if(i && dist[t] == INF) return INF;

这里INF（0x3f3f3f3f）表示不存在最小生成树。

更新res

这里要注意如果i == 0的话是不能更新的。

if(i) res += dist[t];

标记

st[t] = true;

最后一定要更新！！！！！！！！！！

更新的过程和Dijkstra差不多。
代谢一遍然后更新。

for(int j = 1; j <= n; j ++) dist[j] = min(dist[j], g[t][j]);

要是忘记return就尴尬了

return res;

完整：

int n, m, g[N][N], dist[N];
bool st[N];
int prim()
{
    memset(dist, 0x3f, sizeof dist);
    int res = 0;
    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;
        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;
}

作者：cht
链接：https://www.acwing.com/activity/content/code/content/353355/
来源：AcWing
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

复制的。

这四y总的板子:

int n;      // n表示点数
int g[N][N];        // 邻接矩阵，存储所有边
int dist[N];        // 存储其他点到当前最小生成树的距离
bool st[N];     // 存储每个点是否已经在生成树中


// 如果图不连通，则返回INF(值是0x3f3f3f3f), 否则返回最小生成树的树边权重之和
int prim()
{
    memset(dist, 0x3f, sizeof dist);

    int res = 0;
    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;

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

作者：yxc
链接：https://www.acwing.com/blog/content/405/
来源：AcWing
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

~~外边好像打雷了，我也太骄傲了，自己的垃圾怎么能和y总的板子相提并论呢？~~

好了大家看一下题

prim求最小生成树

给定一个n个点m条边的无向图，图中可能存在重边和自环，边权可能为负数。

求最小生成树的树边权重之和，如果最小生成树不存在则输出impossible。

给定一张边带权的无向图G=(V, E)，其中V表示图中点的集合，E表示图中边的集合，n=|V|，m=|E|。

由V中的全部n个顶点和E中n-1条边构成的无向连通子图被称为G的一棵生成树，其中边的权值之和最小的生成树被称为无向图G的最小生成树。

输入格式
第一行包含两个整数n和m。

接下来m行，每行包含三个整数u，v，w，表示点u和点v之间存在一条权值为w的边。

输出格式
共一行，若存在最小生成树，则输出一个整数，表示最小生成树的树边权重之和，如果最小生成树不存在则输出impossible。

数据范围

1≤n≤500,
1≤m≤105,
图中涉及边的边权的绝对值均不超过10000。

输入样例：

输出样例：

本题就是把prim调用一遍。
这里就直接上代码了。

#include<bits/stdc++.h>
using namespace std;
const int N = 510, INF = 0x3f3f3f3f;
int n, m, g[N][N], dist[N];
bool st[N];
int prim()
{
    memset(dist ,0x3f, sizeof dist);
    int res = 0;
    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;
        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()
{
    cin >> n >> m;
    memset(g, 0x3f, sizeof g);
    while(m --)
    {
        int a, b, w;
        cin >>a  >> b >> w;
        g[a][b] = g[b][a] = min(g[a][b], w);
    }
    int ans = prim();
    if(ans == INF) puts("impossible");
    else cout << ans;
    return 0;
}