#include <iostream.h>

#define INFINITY INT_MAX                  //最大值：無窮大
#define MAX_VERTEX_NUM 20                 //最大頂點(diǎn)個(gè)數(shù)
#define MAX   100000                      //最大值

typedef float VRType;                      //頂點(diǎn)關(guān)系類型
typedef char VerTexType;                   //頂點(diǎn)類型 

typedef struct
{VRType adj;}ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];  //帶權(quán)圖的權(quán)值類型

typedef struct
{char vexs[MAX_VERTEX_NUM];        //頂點(diǎn)向量
 AdjMatrix arcs;                   //鄰接矩陣
 int vexnum;                       //頂點(diǎn)數(shù)
}MGraph;                           //圖的種類標(biāo)志

typedef struct
{
 char adjvex;                        //記錄生成樹頂點(diǎn)集合外各頂點(diǎn)距離集合內(nèi)哪個(gè)頂點(diǎn)最近
 VRType lowcost;                     //存放生成樹頂點(diǎn)集合內(nèi)頂點(diǎn)到生成樹外各頂點(diǎn)的各邊上的當(dāng)前最小權(quán)值
}closedge[MAX_VERTEX_NUM];          //最小生成樹的輔助數(shù)組


void CreateGraph(MGraph &G);            //建立一個(gè)圖G的鄰接矩陣
void MiniSpanTree_PRIM(MGraph G, char u);    //用PRIM算法從第u個(gè)頂點(diǎn)出發(fā)構(gòu)造網(wǎng)G的最小生成樹T，輸出T的各條邊
                                             //記錄從頂點(diǎn)集U到V-U的代價(jià)最小的邊的輔助數(shù)組定義
int LocateVex(MGraph G, char u);   //確定頂點(diǎn)在圖G中的位置
int minimum(closedge close);       //求出當(dāng)前最小的邊所依附的集合V-U中的頂點(diǎn)的位置

void main( void )       
{
 int i, j;
 MGraph G;
 
 CreateGraph(G);                      //建立圖G的鄰接矩陣
 for(i=0; i<G.vexnum; i++)            //輸出圖G的鄰接矩陣
 {
  for(j=0; j<G.vexnum; j++)
  {
   cout<<G.arcs[i][j].adj;            //輸出圖G中各條邊的權(quán)值
   cout<<"	";
  }
  cout<<endl;
 }
 MiniSpanTree_PRIM(G, 'a');            //建立最小生成樹
 cin>>i; 
}


void CreateGraph(MGraph &G)
{
 float weigh;                  //定義權(quán)值類型 
 int i,j;
 int count=0;              //設(shè)立一個(gè)計(jì)數(shù)器，記錄當(dāng)前輸入的邊數(shù)
 char v1,v2;               //定義頂點(diǎn)類型
 
cout<<"請輸入辦公室個(gè)數(shù)："<<endl;
cin>>G.vexnum;                  //輸入頂點(diǎn)數(shù)

cout<<"現(xiàn)在請輸入所有這些辦公室的房間號（以字母a-z表示）:";

  for(i=0; i<G.vexnum; i++)          //輸入所有頂點(diǎn)
   cin>>G.vexs[i];
 cout<<endl;
 for(i=0;i<G.vexnum;i++)             //初始化各條邊上的權(quán)值為最大值
   for(j=0;j<G.vexnum;j++)
   G.arcs[i][j].adj=MAX;
	 do                                //構(gòu)造鄰接矩陣
	 { cout<<"請分別輸入兩個(gè)辦公室的房間號&在這兩個(gè)辦公室間布線需要的成本:"<<endl;
		cout<<"提示：為了建成局域網(wǎng)，您至少需要"<<G.vexnum-1<<"根接線，請至少輸入"<<G.vexnum-1<<"組房間號碼"<<endl;

    cout<<"請先輸入第一個(gè)辦公室的房間號，以字母表示（a-z）（如果您已經(jīng)輸入完畢所有房間請按#號鍵確認(rèn)）:"<<endl;
  cin>>v1;                                                   //輸入一條邊依附的頂點(diǎn)
  cout<<endl<<"請?jiān)佥斎氲诙€(gè)辦公室的房間號，以字母表示（a-z）（如果您已經(jīng)輸入完畢所有房間請按#號鍵確認(rèn)）:"<<endl;
  cin>>v2;                                                   //輸入該條邊依附的另一個(gè)頂點(diǎn)
  cout<<endl<<"現(xiàn)在請輸入這兩個(gè)辦公室間布線需要的成本（如果您已經(jīng)輸入完畢所有房間請按0確認(rèn)）:";
  cin>>weigh;                                                 //輸入這條邊上的權(quán)值
  cout<<endl;
   i=LocateVex(G,v1);                                      //確定V1和V2在G中的位置
   j=LocateVex(G,v2);
   
  G.arcs[i][j].adj = weigh;                            //邊<v1,v2>的權(quán)值
  G.arcs[j][i].adj = weigh;                           //置<v1,v2>的對稱邊<v2,v1>
  if(weigh!=0&&v1==G.vexs[i]&&v2==G.vexs[j])           //輸入完一組頂點(diǎn)，統(tǒng)計(jì)一次當(dāng)前圖G的邊數(shù)
  cout<<endl<<"您已經(jīng)輸入了"<<++count<<"組房間號碼"<<endl<<endl;
 
  else cout<<"您一共輸入了"<<count<<"組房間號碼"<<endl;   //若輸入已經(jīng)進(jìn)行完畢，統(tǒng)計(jì)圖G的總邊數(shù)
	 }
  while(v1!='#'||v2!='#'||weigh!=0);                  //若輸入為進(jìn)行完畢，返回DO語句，繼續(xù)輸入下一組頂點(diǎn)及權(quán)值
 
}

void MiniSpanTree_PRIM(MGraph G,char u)       //構(gòu)造并顯示最小生成樹的PRIM算法
{
 int i,j,k= 0;
 closedge close;
 
 k = LocateVex ( G, u );                   //確定第一個(gè)輸入的頂點(diǎn)在圖G中的位置，并從該頂點(diǎn)出發(fā)開始建立最小生成樹T
 for (j=0; j<G.vexnum; j++ )               //輔助數(shù)組close初始化
 {
  if (j!=k)                               
  {
   close[j].adjvex = G.vexs[k];            
   close[j].lowcost = G.arcs[k][j].adj;    
  }
 }
  close[j].lowcost = MAX;                  //若j對應(yīng)的頂點(diǎn)與第一個(gè)輸入的頂點(diǎn)間沒有邊，則令該邊上的權(quán)值為最大值           
  close[j].adjvex = '\0';                  //同時(shí)，令j對應(yīng)的頂點(diǎn)所依附的頂點(diǎn)為\0
  close[k].lowcost = 0;                   //初始，U={u}
  close[k].adjvex = u;
  cout<<"成本最低的接線為:"<<endl;          //輸出成本最低的接線
 for (i = 1; i < G.vexnum; i++)              //選擇其余G.vexnum-1個(gè)頂點(diǎn)
 { 
  k = minimum(close);                     //求出T的下一個(gè)結(jié)點(diǎn)：第K頂點(diǎn)

 
  cout<<close[k].adjvex;              //輸出生成樹的邊
  cout<<"---->";
  cout<<G.vexs[k]<<" ";
  cout<<close[k].lowcost<<endl;
  close[k].lowcost = 0;               //第K頂點(diǎn)并入U(xiǎn)集
  for (j=0; j<G.vexnum; j++)
  {
   if (G.arcs[k][j].adj < close[j].lowcost)           //新頂點(diǎn)并入U(xiǎn)后重新選擇最小邊
   {
    close[j].adjvex = G.vexs[k];
    close[j].lowcost = G.arcs[k][j].adj;
   }
  }
 }
}

int LocateVex(MGraph G, char u)                    //確定輸入的頂點(diǎn)在G中的位置
{ int i;
  for(i=0;i<G.vexnum;i++)
  {if(u==G.vexs[i])return i;}         //輸入的頂點(diǎn)u存在于圖G中
  if(i==G.vexnum&&u!='#')             //輸入的頂點(diǎn)u不存在于圖G中，并且輸入還沒有結(jié)束
  {cout<<"您輸入的房間號碼有錯(cuò)！請重新輸入："<<endl;   //顯示出錯(cuò)，并繼續(xù)輸入下一頂點(diǎn)
  return -1;}
  else {cout<<"您已經(jīng)輸入完畢!";       //輸入完畢
	 return -1;}
  }
 



int minimum(closedge close)       //求當(dāng)前最小邊在頂點(diǎn)集V-U中所依附的頂點(diǎn)位置
{
 int i=0, client = MAX, j;
 while(close[i].adjvex != '\0')         //該頂點(diǎn)仍在V-U中
 {
  if (client > close[i].lowcost && close[i].lowcost != 0)   
  {client = close[i].lowcost;           //修改最小權(quán)值
  j = i; }                              //修改最小邊在頂點(diǎn)集V-U中所依附的頂點(diǎn)位置
    i++;}
  return j;
}