//普萊姆最小生成樹(shù)算法
void Prim(MGraph g,int v0,int &sum)
{
 int lowcost[maxSize],vset[maxSize],v;
 int i,j,k,min;
 v=v0;
 for(i=1;i<=g.n;i++)//初始數(shù)據(jù)
 {
  lowcost[i]=g.edges[v0][i];
  vset[i]=0;
 }
 vset[v0]=1;//并入樹(shù)
 sum=0;
 for(i=0;i<g.n;i++)
 {
  min=INFINITY;
  for(j=0;j<g.n;j++)
  {
   if(vset[j]==0&&lowcost[j]<min)//選出當(dāng)前最小的一個(gè)邊
   {
    min=lowcost[j];
    k=j;
   }
  }
  vset[k]=1;//并入樹(shù)中
  v=k;
  sum+=min;
  for(j=1;j<g.n;j++)
  {
   if(vset[j]==0&&g.edges[v][j]<lowcost[j])
   {
    lowcost[j]=g.edges[v][j];
   }
  }
 }

}

標(biāo)簽：

版權(quán)申明：本站文章部分自網(wǎng)絡(luò)，如有侵權(quán)，請(qǐng)聯(lián)系：west999com@outlook.com
特別注意：本站所有轉(zhuǎn)載文章言論不代表本站觀點(diǎn)！
本站所提供的圖片等素材，版權(quán)歸原作者所有，如需使用，請(qǐng)與原作者聯(lián)系。