prim是設(shè)置一個初始結(jié)點，尋找其周圍最小的邊權(quán)值，并將該結(jié)點作為初始結(jié)點，繼續(xù)尋找現(xiàn)在結(jié)點周圍的邊權(quán)值的最小值，但要注意如果這次尋找的某個邊權(quán)值沒有上次的小的話仍然保留上一次的邊權(quán)值，即lowcast的值將會不變。

1 #include<stdio.h> 2 #include<iostream> 3 #include<string.h> 4 #include<algorithm> 5 using namespace std; 6 const int inf=0x3f3f3f3f;///當(dāng)兩個點之間沒有邊時設(shè)置這兩個邊之間的距離為無窮大 7 const int maxn=110;///數(shù)組的長度 8 int ma[maxn][maxn],lowcost[maxn];///ma[i][j]數(shù)組的用于存儲i,j兩點之間的距離，lowcast[j]用于存儲從標(biāo)記邊k到邊j的邊的長度 9 bool vis[maxn];///用于記錄點是否已經(jīng)加入到樹中 10 int nodenum,sum; 11 void prim() 12 { 13 int temp,k; 14 sum=0; 15 memset(vis,false,sizeof(vis)); 16 vis[1]=true;///從1開始查詢 17 for(int i=1;i<=nodenum;i++) 18 { 19 lowcost[i]=ma[1][i]; 20 21 } 22 for(int i=1;i<=nodenum;i++){ 23 temp=inf;///temp用于存儲最短的距離 24 for(int j=1;j<=nodenum;j++){ 25 if(!vis[j]&&temp>lowcost[j]) 26 temp=lowcost[k=j];///在賦值的同時把j的值賦給k，下次就從k開始向其他結(jié)點尋找 27 if(temp==inf)break;///如果temp值沒有改變的話就證明該點不與其它點連通，最小生成樹建立失敗，跳出循環(huán) 28 vis[k]=true; 29 sum+=temp; 30 for(int j=1;j<=nodenum;j++){ 31 if(!vis[j]&&lowcost[j]>ma[k][j])///此時lowcast中其實還含有上一個結(jié)點到j(luò)的距離，若ma[k][j]不足夠小的話lowcast的值將不變 32 lowcost[j]=ma[k][j]; 33 } 34 } 35 } 36 37 } 38 int main() 39 { 40 int a,b,cost,edgenum; 41 while(cin>>nodenum&&nodenum){ 42 memset(ma,inf,sizeof(ma));///初始化最開始所有的點之間都不關(guān)聯(lián) 43 edgenum=nodenum*(nodenum-1)/2;///edgenum是所有點之間都有邊相連的邊的個數(shù) 44 for(int i=1;i<=edgenum;i++){ 45 cin>>a>>b>>cost; 46 if(cost<ma[a][b]){ 47 ma[a][b]=ma[b][a]=cost;///無向圖的邊沒有方向 48 } 49 } 50 prim(); 51 cout<<sum<<endl; 52 } 53 } View Code

?

轉(zhuǎn)載于:https://www.cnblogs.com/shangjindexiaoqingnian/p/5846665.html

總結(jié)

以上是生活随笔為你收集整理的最小生成树之prim的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。