// algo7-2.cpp 實現算法7.9的程序
 #include"c1.h"
 typedef int VRType;
 typedef char InfoType;
 #define MAX_NAME 3 // 頂點字符串的最大長度+1
 #define MAX_INFO 20 // 相關信息字符串的最大長度+1
 typedef char VertexType[MAX_NAME];
 #include"c7-1.h"
 #include"bo7-1.cpp"

 typedef struct
 { // 記錄從頂點集U到V-U的代價最小的邊的輔助數組定義
   VertexType adjvex;
   VRType lowcost;
 }minside[MAX_VERTEX_NUM];

 int minimum(minside SZ,MGraph G)
 { // 求closedge.lowcost的最小正值
   int i=0,j,k,min;
   while(!SZ[i].lowcost)
     i++;
   min=SZ[i].lowcost; // 第一個不為0的值
   k=i;
   for(j=i+1;j<G.vexnum;j++)
     if(SZ[j].lowcost>0)
       if(min>SZ[j].lowcost)
       {
         min=SZ[j].lowcost;
         k=j;
       }
   return k;
 }

 void MiniSpanTree_PRIM(MGraph G,VertexType u)
 { // 用普里姆算法從第u個頂點出發構造網G的最小生成樹T,輸出T的各條邊。算法7.9
   int i,j,k;
   minside closedge;
   k=LocateVex(G,u);
   for(j=0;j<G.vexnum;++j) // 輔助數組初始化
   {
     if(j!=k)
     {
       strcpy(closedge[j].adjvex,u);
       closedge[j].lowcost=G.arcs[k][j].adj;
     }
   }
   closedge[k].lowcost=0; // 初始,U={u}
   printf("最小代價生成樹的各條邊為:\n");
   for(i=1;i<G.vexnum;++i)
   { // 選擇其余G.vexnum-1個頂點
     k=minimum(closedge,G); // 求出T的下一個結點：第K頂點
     printf("(%s-%s)\n",closedge[k].adjvex,G.vexs[k]); // 輸出生成樹的邊
     closedge[k].lowcost=0; // 第K頂點并入U集
     for(j=0;j<G.vexnum;++j)
       if(G.arcs[k][j].adj<closedge[j].lowcost)
       { // 新頂點并入U集后重新選擇最小邊
         strcpy(closedge[j].adjvex,G.vexs[k]);
         closedge[j].lowcost=G.arcs[k][j].adj;
       }
   }
 }

 void main()
 {
   MGraph G;
   CreateAN(G);
   MiniSpanTree_PRIM(G,G.vexs[0]);
 }