算法板子-Prime算法（带注释）

​

Prime算法是基于贪心思想的一种最小生成树算法

• 需要的存储结构

const int N=505 
const int INF=0x3f3f3f3f;  //int最大值
int n,m 
int ans=0;  //存储最小生成树权值和结果
int v[N][N]  //存储图
int d[N];	 //单点直接连接其他点的最小权值
bool book[N]={0};  //记录当前点是否被选择

• 初始化

void init(){
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            v[i][j]=INF;//将邻接矩阵中所有点置最大，方便后续贪心操作
        }
        d[i]=INF;//同理
    }
    for(int i=1;i<=m;i++){
        int x,y,z;
        cin>>x>>y>>z;
        if(x!=y){//判环
            v[x][y]=min(z,v[x][y]); //判重边
            v[y][x]=min(z,v[y][x]); //判重边
        }
    }
}

• prime算法本体

void prim(){
    book[1]=1; //选取点1作为起始
    d[1]=0; //自己到自己，距离置0
    for(int i=2;i<=n;i++)d[i]=min(v[1][i],d[i]); //初始化点1的所有连接点，并将所有连接点的权值更新至d数组
    for(int i=2;i<=n;i++){
        int temp=INF;//该点连接的最小权值
        int t=-1;//此次选取的点
        for(int j=2;j<=n;j++){
            if(!book[j]&&d[j]<temp){//选取没被选过的点，并且贪心地选择最小的
                temp=d[j];
                t=j;
            }
        }
        if(t==-1){//说明没有点被选中，无法构成生成树，只能构成生成森林，将ans置一个数据范围无法达到的数，方便后续判断
            ans=INF;
            return;
        }
        ans+=temp;// 权值和++
        book[t]=1;// 将当前点标记为走过
        for(int j=2;j<=n;j++){
            d[j]=min(d[j],v[t][j]); //以当前点为原点，当前点所连接的点更新d数组
        }
    }
}

• 完整代码

#include<bits/stdc++.h>
using namespace std;

const int N=505 
const int INF=0x3f3f3f3f;  //int最大值
int n,m 
int ans=0;  //存储最小生成树权值和结果
int v[N][N]  //存储图
int d[N];	 //单点直接连接其他点的最小权值
bool book[N]={0};  //记录当前点是否被选择

void init(){
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            v[i][j]=INF;//将邻接矩阵中所有点置最大，方便后续贪心操作
        }
        d[i]=INF;//同理
    }
    for(int i=1;i<=m;i++){
        int x,y,z;
        cin>>x>>y>>z;
        if(x!=y){//判环
            v[x][y]=min(z,v[x][y]); //判重边
            v[y][x]=min(z,v[y][x]); //判重边
        }
    }
}

void prim(){
    book[1]=1; //选取点1作为起始
    d[1]=0; //自己到自己，距离置0
    for(int i=2;i<=n;i++)d[i]=min(v[1][i],d[i]); //初始化点1的所有连接点，并将所有连接点的权值更新至d数组
    for(int i=2;i<=n;i++){
        int temp=INF;//该点连接的最小权值
        int t=-1;//此次选取的点
        for(int j=2;j<=n;j++){
            if(!book[j]&&d[j]<temp){//选取没被选过的点，并且贪心地选择最小的
                temp=d[j];
                t=j;
            }
        }
        if(t==-1){//说明没有点被选中，无法构成生成树，只能构成生成森林，将ans置一个数据范围无法达到的数，方便后续判断
            ans=INF;
            return;
        }
        ans+=temp;// 权值和++
        book[t]=1;// 将当前点标记为走过
        for(int j=2;j<=n;j++){
            d[j]=min(d[j],v[t][j]); //以当前点为原点，当前点所连接的点更新d数组
        }
    }
}

int main(void){
    cin>>n>>m;
    init();
    prim();
    if(ans==INF){
        cout<<"impossible";
    }else{
        cout<<ans;
    }
}

• 本体样例题目背景来源

AcWing-858. Prim算法求最小生成树