最小生成树——prim算法（内含爆肝两晚的保姆级代码）_最小生成树prim算法

一.概述（看不了一点）

在一给定的无向图G = (V, E) 中，(u, v) 代表连接顶点 u 与顶点 v 的边，而 w(u, v) 代表此的边权重，若存在 T 为 E 的子集（即）且为无循环图，使得的 w(T) 最小，则此 T 为 G 的最小生成树（Minimum Spanning Tree(MST) ）。最小生成树其实是最小权重生成树的简称。

简单来说，就是给你很多个点，然后求将这些点连接起来的所有边的最小长度和。

二.图解（保你看懂）

待我们先看一道题理解一下在什么情况下用prim算法求最小生成树

题目描述

如题，给出一个无向图，求出最小生成树，如果该图不连通，则输出 orz。

输入格式

第一行包含两个整数 N,M，表示该图共有 N 个结点和 M 条无向边。

接下来M 行每行包含三个整数Xi​,Yi​,Zi​，表示有一条长度为 Zi​ 的无向边连接结点 Xi​,Yi​。

输出格式

如果该图连通，则输出一个整数表示最小生成树的各边的长度之和。如果该图不连通则输出 orz。

输入输出样例

输入 #1

4 5
1 2 2
1 3 2
1 4 3
2 3 4
3 4 3

输出 #1

7

我们现在有一个无向图（就是一张图），这时候我们要从点1开始然后将所有点连接起来，计算边的长度。现在我们构建两个集合S（红色的点），V（蓝色的点），S集合中存放的是已近加入最小生成树的点，V集合中存放的是还没有加入最小生成树的点。显然刚开始时所有的点都在V集合中。

1.我们开始时初始化其他点到点1的距离即到集合S的距离都为正无穷

2.我们将ans作为所求值，刚开始应该记为零。每一次我们选择离集合里面点有最近距离的点加入集合中同时更新dist数组，以及ans的值

3.在目前情况下，S集合中只有点1，这时距离S集合最近的点应该为点2，我们将点2加入集合S中，同时将dist数组和ans的值进行更新。

4.加入点2后，现在集合中有的边为23，即ans更新为23，同时对于没有在集合中的点到集合的距离进行更新，如点7应该由36更新为1。

5.然后重复上面所有步骤，直到我们的集合中包含了所有的点......

6.直到最后，我们可以发现这些点如果能被连接起来，那么需要的最小的边的长度应该为57，即权值和为57。

三.代码来了（我们还是借用这道题来展示代码）

题目描述

如题，给出一个无向图，求出最小生成树，如果该图不连通，则输出 orz。

输入格式

第一行包含两个整数 N,M，表示该图共有 N 个结点和 M 条无向边。

接下来M 行每行包含三个整数Xi​,Yi​,Zi​，表示有一条长度为 Zi​ 的无向边连接结点 Xi​,Yi​。

输出格式

如果该图连通，则输出一个整数表示最小生成树的各边的长度之和。如果该图不连通则输出 orz。

输入输出样例

输入 #1

4 5
1 2 2
1 3 2
1 4 3
2 3 4
3 4 3

输出 #1

7

这里我们说两种代码，第一种可以理解一下（方法没错，这道题ac不了的原因是他给的范围很大是第一种方法的二维数组爆了），第二种就是是为了防止有些恶心题目开的范围太大使用的优化算法（这个可以ac哦）（第一种改了一个晚上才弄出来，第二种又爆肝了一晚上）。不说了，步入正题。

1.正常（符合上面图解）的prim代码

#include <bits/stdc++.h>
using namespace std;
const int N = 10001;
const int INF = 998244353;
int g[N][N], dist[N], n, m, res;
bool vis[N];
void prim()
{
    dist[1] = 0;//把点1加入集合S，点1在集合S中，将它到集合的距离初始化为0
    vis[1] = true;//表示点1已经加入到了S集合中
    for (int i = 2; i <= n; i++)
    {
        dist[i] = min(dist[i], g[1][i]);
    }//用点1来更新dist数组
    for (int i = 2; i <= n; i++) //计数器，表示选了几次了，正在选第几个点
    {
        int temp = INF;//初始化距离为无穷大
        int t = -1;//接下来去寻找离集合S最近的点加入到集合中，用t记录这个点的下标
        for (int j = 2; j <= n; j++) //判断正在几号点
        {
            //如果这个点没有加入集合S，而且这个点到集合的距离小于temp就将下标赋给t
            if (vis[j] == false && dist[j] < temp)
            {
                temp = dist[j];//更新集合V到集合S的最小值
                t = j;//把点赋给t
            }
        }
        if (t == -1)//表明没有适合的点,将res赋值正无穷表示构建失败，结束函数
        {
            res = INF;
            return;
        }
        vis[t] = true;//表明这个点找到过了，不用再使用这个点了
        res += dist[t]; //注意是dist[t]而不是dist[i]，这里的i只起到计次数作用
        for (int j = 2; j <= n; j++)
        {
            dist[j] = min(dist[j], g[t][j]);//取较小的dist[i]
        }
    }
}
int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            g[i][j] = INF; //设刚开始所有点之间的距离为无穷大
        }
        dist[i] = INF; //点到集合上任意一个点都为无穷大
    }
    for (int i = 1; i <= m; i++)
    {
        int u, v, w;
        cin >> u >> v >> w;
        g[u][v] = g[v][u] = min(w,g[u][v]); // u与v之间的距离为w
    }
    prim();
    if (res == INF)
    {
        cout << "orz" << endl;//如果还是无穷大则输出
    }
    else
    {
        cout << res << endl;//不是无穷大则输出正常值
    }
    system("pause");
    return 0;
}

2.优化prim算法（队列）

#include <bits/stdc++.h>
using namespace std;
const int N=20001;
int dist[N];//到集合的距离
bool vis[N];//标记是否存入集合中
int n,m,ans;
typedef struct node{
    int pos;
    int dis;
    bool operator<(const node &x) const
    {
        return x.dis<dis;
        //从小到大排序
    }
}node;
typedef struct edge{
    int v;
    int w;      
}edge;
vector<edge> connects[N];//点之间的距离
const int INF=998244353;
void init(){
    for(int i=1;i<=n;i++){
        dist[i]=INF;//刚开始距离全部初始化为无穷大
        vis[i]=false;//表示都还没有访问
    }
}
void prim(){
    dist[1]=0;//1的距离为零
    vis[1]=true;//表示1访问过了，已存入集合中
    priority_queue<node> q;//构建优先队列，优先计算有多条边的两个点的较小的边的值
    q.push({1,0});//将点1存入
    while(!q.empty()){
        int pos=q.top().pos;
        int dis=q.top().dis;
        q.pop();
        vis[pos]=true;//存入就标记
        for(int i=0;i<connects[pos].size();i++){//将一个点周围所有点进行搜索
            int v=connects[pos][i].v;
            int w=connects[pos][i].w;
            if(vis[v]==1){//表示已经存入了，不用再进行下面操作了
                continue;
            }
            if(dist[v]>w){//如果距离小于dist数组距离就更新
                dist[v]=w;
                q.push({v,dist[v]});
            }
        }
    }
    for(int i=1;i<=n;i++){
        ans+=dist[i];//最后将所有最小值加起来
    }
    if(ans>=INF){//如果依然是无穷大，表示为构建成功最小生成树，输出orz
        cout<<"orz"<<endl;
    }else{
        cout<<ans<<endl;//不是无穷大则正常输出
    }
}
int main(){
    cin>>n>>m;
    init();
    for(int i=1;i<=m;i++){
        int u,v,w;
        cin>>u>>v>>w;//开始存入点之间的距离
        connects[u].push_back({v,w});
        connects[v].push_back({u,w});
    }
    prim();
    system("pause");
    return 0;
}

最后，完结撒花！

不要忘了轻轻关注一下这位为了这个算法爆肝了两个晚上的某帅气（趁现在还没怎么掉头发）博主！