最小生成树－prim算法.txt

数据结构C对图的操作算法

#define M 30
#define MAX 100 //相当于无穷值

void minispantree_PRIM(int ad[][M],int n) //用邻接矩阵ad存储图
{  int i,j,k,p,q,wm;
   q=p=n-1;
   ad[q][q]=1; //从矩阵ad的最后一个结点ad[n-1][n-1]开始查找
   for(k=0;k<(n-1);k++)
   {  wm=MAX; //wm用来存储查找出来的未被处理过的最小权值
      for(i=0;i<n;i++)
         if(ad[i][i]==1)//如果对角线为1，说明这个结点是最小生成树中的一个结点
            for(j=0;j<n;j++) //就在这一行上查找未被处理过的最小权值并存放在wm中
               if((ad[j][j]==0)&&(ad[i][j]<wm))
               {   wm=ad[i][j];
                   p=i;
                   q=j;//p、q存储找到的最小权值的行和列
               }

      ad[q][q]=1;
      printf("%d %d %d\n",p+1,q+1,ad[p][q]);
      if(p>q)  ad[p][q]=-ad[p][q];
      else     ad[q][p]=-ad[q][p];
   }
}