普莱姆最小生成树算法

//普莱姆最小生成树算法
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++)//初始数据
 {
  lowcost[i]=g.edges[v0][i];
  vset[i]=0;
 }
 vset[v0]=1;//并入树
 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)//选出当前最小的一个边
   {
    min=lowcost[j];
    k=j;
   }
  }
  vset[k]=1;//并入树中
  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];
   }
  }
 }

}

标签：

版权申明：本站文章部分自网络，如有侵权，请联系：west999com@outlook.com
特别注意：本站所有转载文章言论不代表本站观点！
本站所提供的图片等素材，版权归原作者所有，如需使用，请与原作者联系。