// algo7-4.cpp 實現算法7.9的程序
 #include"c1.h"
 #include"func7-1.cpp" // 包括頂點信息類型的定義及對它的操作
 #include"func7-2.cpp" // 包括弧(邊)的相關信息類型的定義及對它的操作
 #include"c7-1.h" // 圖的數組(鄰接矩陣)存儲結構
 #include"bo7-1.cpp" // 圖的數組(鄰接矩陣)存儲結構的基本操作

 typedef struct
 { // 記錄從頂點集U到V-U的代價最小的邊的輔助數組定義
   int adjvex; // 頂點集U中到該點為最小權值的那個頂點的序號
   VRType lowcost; // 那個頂點到該點的權值(最小權值)
 }minside[MAX_VERTEX_NUM];

 int minimum(minside SZ,MGraph G)
 { // 求SZ.lowcost的最小正值，并返回其在SZ中的序號
   int i=0,j,k,min;
   while(!SZ[i].lowcost) // 找第1個值不為0的SZ[i].lowcost的序號
     i++;
   min=SZ[i].lowcost; // min標記第1個不為0的值
   k=i; // k標記該值的序號
   for(j=i+1;j<G.vexnum;j++) // 繼續向后找
     if(SZ[j].lowcost>0&&SZ[j].lowcost<min) // 找到新的更小的正值
     { min=SZ[j].lowcost; // min標記此正值
       k=j; // k標記此正值的序號
     }
   return k; // 返回當前最小正值在SZ中的序號
 }

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

 void main()
 {
   MGraph g;
   char filename[13]; // 存儲數據文件名(包括路徑)
   printf("請輸入數據文件名：");
   scanf("%s",filename);
   CreateFromFile(g,filename,0); // 創建無相關信息的網
   Display(g); // 輸出無向網g
   MiniSpanTree_PRIM(g,g.vexs[0]);
   // 用普里姆算法從第1個頂點出發輸出g的最小生成樹的各條邊
 }