• 普里姆算法

    普里姆算法

    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. }