普萊姆最小生成樹算法

//普萊姆最小生成樹算法
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];
   }
  }
 }
}
</pre>