模板:Prim

xiaoxiao2021-02-28  10

思路:

先把1到 i 的边放进lowcost(反着找结果相同)

找lowcost中 1 到 i 的最小值,记录下标(id);

再把 id到 i 放进lowcost (lowcost[ id ]赋为-1,表示已经收录过了)

mst 可以作为中间变量输出最小树;

const int maxn=110; const int maxcost=999999999; int graph[maxn][maxn],lowcost[maxn]; int prim(int n){ int lowcost[maxn]; int mst[maxn]; int i,j,minn,minid,sum=0; for(i=2;i<=n;i++){ //lowcost初始化 lowcost[i]=graph[1][i]; mst[i]=1; } mst[1]=0; for(i=2;i<=n;i++){ minn=maxcost; minid=0; for(j=2;j<=n;j++){ if(lowcost[j]<minn&&lowcost[j]!=-1){ //上一层已经把找过的赋为-1 minn=lowcost[j]; minid=j; } } if(minn==maxcost) return -1; //不连通 //printf("%c - %c : %d\n", mst[minid] + 'A' - 1, minid + 'A' - 1, min); sum+=minn; lowcost[minid]=-1; for(j=2;j<=n;j++){ //找路径(权值),谁小换谁,相同不换。 if(graph[minid][j]<lowcost[j]){ lowcost[j]=graph[minid][j]; mst[j]=minid; //mst中每一个都是minid,到下次时可以表示起点,然后 - 下一个minid } } } return sum; } /* //若从s开始:把1换为s即可 //如果在n的m个点里找最小生成树,可以引入temp[]数组存放n的下标。把i,j换成temp[]即可 int prim(int s,int n){       int lowcost[maxn];       int i,j,minn,minid,sum=0;       for(int i=1;i<=n;i++)           lowcost[i]=graph[s][i];       lowcost[s]=-1;       for(int i=2;i<=n;i++){           int minn=inf;           int minid=0;           for(int j=1;j<=n;j++){               if(lowcost[j]!=-1&&lowcost[j]<minn){                   minid=j;                   minn=lowcost[j];               }           }           sum+=minn;           lowcost[minid]=-1;           for(int j=1;j<=n;j++)               if(lowcost[j]>graph[minid][j])                   lowcost[j]=graph[minid][j];       }       return sum;   }   */

转载请注明原文地址: https://www.6miu.com/read-1100016.html

最新回复(0)