[讲解]prim算法<最小生成树>

最小生成树的方法一般比较常用的就是kruskal和prim算法

一个是按边从小到大加，一个是按点从小到大加，两个方法都是比较常用的，都不是很难。。。

kruskal算法在本文里我就不讲了，本文的重点是讲讲prim算法，之前一直没学过，只是了解了思想，原本以为很难，结果很好理解

prim 即可以用过邻接矩阵又可以用邻接链表，不过邻接链表的时间优化不了多少，但是还是可以优化很多空间的

prim算法是先枚举第一个点，将选好的点加入点集V，没选的点在点集U，然后在U集中找距离V集最近一个点，然后将其加入U集

我们还是用图来举例说明

我们来模拟一遍这个过程。。。

首先，lowcost表示从当前点到V集的最小距离，mst表示当前点到V集最小的那个V集的点

我们先从1点开始。。。

判断和1点相连的点，lowcost[2]=6,lowcost[3]=1,lowcost[4]=5,lowcost[5]=lowcost[6]=inf

　　　　　　　　　 mst[2]=1,mst[3]=1,mst[4]=1;

然后跑整个图的点，找到最小的lowcost并将这个点加入V集，从U集删除（删除操作即为把lowcost赋值为0）

因为V集多了3，就更新整个图lowcost[2]=5,lowcost[4]=5,lowcost[5]=6,lowcost[6]=4;

　　　　　　　　　　　　　mst[2]=3,mst[4]=1,mst[5]=3,mst[6]=3;

然后找整个U集发现lowcost最小是6点，V集加入6点，更新U集

lowcost[2]=5,lowcost[4]=2,lowcost[5]=6

mst[2]=3,mst[4]=6,mst[5]=3

然后找lowcost最小的4点，加入V集，更新U集

lowcost[2]=5,lowcost[5]=6

mst[2]=3,mst[5]=3

找lowcost最小的点2，加入V集，更新U集

lowcost[5]=3,mst[5]=2

加入V集，所有点都已经加入，完成操作，输出ans=15

 #include<cstdio>

 #include<cstring>

 #include<iostream>

 #include<cmath>

 #include<queue>

 #include<algorithm>

 #include<cstdlib>

 #define maxn 1005

 using namespace std;

 int n,m,dis[maxn][maxn],ans;

 int lowcost[maxn],mst[maxn];

 int read(){

     int xx=,ff=;char ch=getchar();

     while(ch<''||ch>''){if(ch=='-')ff=-;ch=getchar();}

     while(ch>=''&&ch<=''){xx=xx*+ch-'';ch=getchar();}

     return xx*ff;

 }

 void prim(int u){

     for(int j=;j<=n;j++){

         if(dis[u][j]>){

             lowcost[j]=dis[u][j];mst[j]=u;

         }

     }

     mst[u]=;lowcost[u]=;

     int minid=,minn=0x3f3f3f,tot=;

     while(tot<n){

         minid=,minn=0x3f3f3f;

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

             if(lowcost[i]!=&&lowcost[i]<minn){

                 minn=lowcost[i];

                 minid=i;

             }

         }

         tot++;

         ans+=minn;

         mst[minid]=;lowcost[minid]=;

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

             if(lowcost[i]!=&&dis[minid][i]<lowcost[i]){

                 lowcost[i]=dis[minid][i];

                 mst[i]=minid;

             }

         }

     }

 }

 int main(){

     n=read();m=read();

     memset(dis,0x3f3f3f,sizeof(dis));

     for(int i=;i<=m;i++){

         int x,y,v;

         x=read();y=read();v=read();

         dis[x][y]=dis[y][x]=v;

     }

     prim();

     printf("%d\n",ans);

 }

 /*

 6 10

 1 3 1

 1 2 6

 1 4 5

 2 3 5

 3 4 5

 2 5 3

 3 5 6

 5 6 6

 3 6 4

 4 6 2

 */

prim

巴特西

[讲解]prim算法<最小生成树>

最新文章

热门文章