普里姆算法

  1. #include <stdio.h>
  2. #define MAXVEX 100
  3. #define INF 32767       /*INF表示∞*/
  5. void Prim(int cost[][MAXVEX],int n,int v)
  6. /*输出最小生成树的每条边*/
  7. {
  8.     int lowcost[MAXVEX],min;
  9.     int closest[MAXVEX],i,j,k;
  10.     for (i=0;i<n;i++)              /*给lowcost[]和closest[]置初值*/
  11.     {    
  12.         lowcost[i]=cost[v][i];
  13.             closest[i]=v;
  14.     }
  15.     for (i=1;i<n;i++)              /*找出n-1个顶点*/
  16.     {   
  17.         min=INF;
  18.         for (j=0;j<n;j++)       /*在(V-U)中找出离U最近的顶点k*/
  19.             if (lowcost[j]!=0 && lowcost[j]<min) 
  20.             {    
  21.                 min=lowcost[j];
  22.                 k=j;  
  23.             }
  24.         printf("  边(%d,%d)权为:%d\n",closest[k],k,min);
  25.         lowcost[k]=0;             /*标记k已经加入U*/
  26.         for (j=0;j<n;j++)       /*修改数组lowcost和closest*/
  27.             if (cost[k][j]!=0 && cost[k][j]<lowcost[j]) 
  28.             {    
  29.                 lowcost[j]=cost[k][j];
  30.                 closest[j]=k; 
  31.             }
  32.     }
  33. }
  35. void main()
  36. {
  37.     int n=7;
  38.     int cost[7][MAXVEX]={
  39.         {0,50,60,INF,INF,INF,INF},
  40.         {50,0,INF,65,40,INF,INF},
  41.         {60,INF,0,52,INF,INF,45},
  42.         {INF,65,52,0,50,30,42},
  43.         {INF,40,INF,50,0,70,INF},
  44.         {INF,INF,INF,30,70,0,INF},
  45.         {INF,INF,45,42,INF,INF,0}};
  46.     printf("最小生成树:\n");Prim(cost,n,0);
  47. }