//* * * * * * * * * * * * * * * * * * * * * * * *
//*CHAPTER          :5  (5_2)                   *
//*PROGRAM          :最小代價生成樹             *
//*CONTENT          :普里姆算法                 *
//* * * * * * * * * * * * * * * * * * * * * * * *
#include <dos.h>
#include <conio.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define INFINITY 30000    //定義一個權值的最大值
#define MAX_VERTEX_NUM 20 //圖的最大頂點數
typedef struct
{int arcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; //鄰接矩陣
 int vexnum,arcnum;                //圖的當前頂點和邊數
}Graph;
typedef struct
{int adjvex;  //某頂點與已構造好的部分生成樹的頂點之間權值最小的頂點
 int lowcost; //某頂點與已構造好的部分生成樹的頂點之間的最小權值
}ClosEdge[MAX_VERTEX_NUM]; //用普里姆算法求最小生成樹時的輔助數組
void CreateGraph(Graph &);    //生成圖的鄰接矩陣 
void MiniSpanTree_PRIM(Graph,int); //用普里姆算法求最小生成樹
int  minimum(ClosEdge,int); //在普里姆算法中求下一個結點
void main()
{Graph G;  //采用鄰接矩陣結構的圖
 char j='y';
 int u;
/* textbackground(3);  //設定屏幕顏色
 textcolor(15);
 clrscr();*/
 //------------------程序解說----------------------------
 printf("本程序將演示構造圖的最小代價生成樹。\n");
 printf("首先輸入圖的頂點數和弧數.\n格式：頂點數，弧數；例如:4,4\n");
 printf("接著輸入各條弧(弧尾,弧頭)和弧的權值。\n");
 printf("格式:弧尾，弧頭，權值；例如\n1,2,1\n1,3,2\n2,4,3\n3,4,4\n");
 printf("程序將會構造該圖的最小代價生成樹。\n");
 printf("并顯示該最小生成樹。\n1,2\n1,3\n2,4\n");
 //------------------------------------------------------
 while(j!='N'&&j!='n')
      {printf("請輸入圖的頂點和弧數:");
       scanf("%d,%d",&G.vexnum,&G.arcnum); //輸入圖的頂點數和邊數
       CreateGraph(G);       //生成鄰接矩陣結構的圖
       printf("從哪一頂點開始:");
       scanf("%d",&u);  //輸入普里姆算法中的起始頂點
       MiniSpanTree_PRIM(G,u); //普里姆算法求最小生成樹
       printf("最小代價生成樹構造完畢，繼續進行嗎?(Y/N)");
       scanf(" %c",&j);
     }
}

void CreateGraph(Graph &G)
{//構造鄰接矩陣結構的圖G
 int i,j;
 int start,end,weight;
 for(i=1;i<=G.vexnum;i++)
    for(j=1;j<=G.vexnum;j++)
      G.arcs[i][j]=INFINITY; //初始化鄰接矩陣
 printf("輸入弧和其權值，格式：弧尾，弧頭，權值\n");
 for(i=1;i<=G.arcnum;i++)
   {scanf("%d,%d,%d",&start,&end,&weight); //輸入邊的起點和終點及權值
    G.arcs[start][end]=weight; 
    G.arcs[end][start]=weight;
   }
}
void MiniSpanTree_PRIM(Graph G,int u)
{//從第u個頂點出發構造圖G的最小生成樹
 ClosEdge closedge;
 int i,j,k;
 printf("最小代價生成樹:\n");
 for(j=1;j<=G.vexnum;j++) //輔助數組初始化
   if(j!=u)
     {closedge[j].adjvex=u;
      closedge[j].lowcost=G.arcs[u][j]; 
     }
 closedge[u].lowcost=0; //初始，U={u}
 for(i=1;i<G.vexnum;i++) //選擇其余的G.vexnum-1個頂點
   {k=minimum(closedge,G.vexnum); //求出生成樹的下一個頂點
    printf("%d,%d\n",closedge[k].adjvex,k); //輸出生成樹的邊
    closedge[k].lowcost=0;   //第k頂點并入U集
    for(j=1;j<=G.vexnum;j++) //新頂點并入U后，重新選擇最小邊
      if(G.arcs[k][j]<closedge[j].lowcost)
	{closedge[j].adjvex=k;
	 closedge[j].lowcost=G.arcs[k][j];
	}
    }
}
int minimum(ClosEdge cl,int vnum)
{//在輔助數組cl[vnum]中選擇權值最小的頂點，并返回其位置
 int i;
 int w,p;
 w=INFINITY;
 for(i=1;i<=vnum;i++)
  if(cl[i].lowcost!=0&&cl[i].lowcost<w)
     {w=cl[i].lowcost;p=i;}
 return p;
}