// 董麗.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include <iostream>
#include <malloc.h>
using namespace std; 
#define int_max 0
#define inf 9999 
#define max 20
//…………………………………………鄰接矩陣定義……………………
typedef struct ArcCell
{
 int adj;
 char *info;
}ArcCell,AdjMatrix[20][20];
typedef struct 
{
 char vexs[20];
 AdjMatrix arcs;
 int vexnum,arcnum;
}MGraph_L;
//^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
int localvex(MGraph_L G,char v)//返回V的位置
{
 int i=0;
 while(G.vexs[i]!=v)
 {
  ++i;
 }
 return i;
}

int creatMGraph_L(MGraph_L &G)//創建圖用鄰接矩陣表示
{
 char v1,v2;
 int i,j,w;
 cout<<endl;
 cout<<endl<<endl;
 cout<<"★★★★★★★★★★★★★你好!歡迎進入最小生成樹★★★★★★★★★★★★★★★"<<endl<<endl<<endl;
 cout<<"            ◎◎◎◎◎◎◎◎◎◎◎◎◎◎◎◎◎◎◎◎◎◎◎◎◎◎                "<<endl<<endl;
 cout<<"----------------------------創建城市分布圖(無向圖)------------------------------"<<endl;
 cout<<endl;
 cout<<endl;
 cout<<endl<<"請輸入城市和道路的個數(注：中間用空格連接):";
 cin>>G.vexnum>>G.arcnum;
 for(i=0;i!=G.vexnum;++i)
 {
  cout<<endl;
  cout<<"輸入城市名稱----"<<i<<endl;
  cin>>G.vexs[i];
 }
 for(i=0;i!=G.vexnum;++i)
  for(j=0;j!=G.vexnum;++j)
  { 
   G.arcs[i][j].adj=int_max;
   G.arcs[i][j].info=NULL;
  }
 for(int k=0;k!=G.arcnum;++k)
  { 
   cout<<"輸入一條道路連接的城市名稱和長度(注：中間用空格連接):"<<endl;
   cin>>v1>>v2>>w;//輸入一條邊依附的兩點及權值
   i=localvex(G,v1);//確定頂點V1和V2在圖中的位置
   j=localvex(G,v2);
   G.arcs[i][j].adj=w;
   G.arcs[j][i].adj=w;
  }
  system("cls");
  return G.vexnum;
}
void ljjzprint(MGraph_L G)
{
 int i,j;
 for(i=0;i!=G.vexnum;++i)
  {cout<<"                      ";
   for(j=0;j!=G.vexnum;++j)
   printf("%-8d",G.arcs[i][j].adj);
   cout<<endl;
   cout<<endl;
   cout<<endl;
  }
}
int visited[max];//訪問標記
int we;
typedef struct arcnode//弧結點
{
 int adjvex;//該弧指向的頂點的位置
 struct arcnode *nextarc;//弧尾相同的下一條弧
 char *info;//該弧信息
}arcnode;
typedef struct vnode//鄰接鏈表頂點頭接點
{
 char data;//結點信息
 arcnode *firstarc;//指向第一條依附該結點的弧的指針
}vnode,adjlist;
    typedef struct//圖的定義
{
 adjlist vertices[max];
 int vexnum,arcnum;
 int kind;
}algraph;

int prim(int g[][max],int n) //最小生成樹PRIM算法
{
 int lowcost[max],prevex[max]; //LOWCOST[]存儲當前集合U分別到剩余結點的最短路徑
         //prevex[]存儲最短路徑在U中的結點
 int i,j,k,min;
 int sum=0; 
 for(i=2;i<=n;i++) //n個頂點，n-1條邊 
 {
  lowcost[i]=g[1][i]; //初始化 
  prevex[i]=1; //頂點未加入到最小生成樹中 
 } 
 lowcost[1]=0; //標志頂點1加入U集合 
 for(i=2;i<=n;i++) //形成n-1條邊的生成樹 
 {
  min=inf; 
  k=0; 
  for(j=2;j<=n;j++) //尋找滿足邊的一個頂點在U,另一個頂點在V的最小邊 
   if((lowcost[j]<min)&&(lowcost[j]!=0)) 
   {
    min=lowcost[j]; 
    k=j; 
   } 
   cout<<endl;
   cout<<endl;
  printf("                         邊：(%d,%d)    代價：%d\t",prevex[k]-1,k-1,min); 
  sum+=min;
  lowcost[k]=0; //頂點k加入U 
  for(j=2;j<=n;j++) //修改由頂點k到其他頂點邊的權值 
   if(g[k][j]<lowcost[j]) 
   {
    lowcost[j]=g[k][j]; 
    prevex[j]=k; 
   } 
  printf("\n"); 
 }  
cout<<endl;
cout<<endl;
cout<<endl;
cout<<"                          最小生成樹的代價:";
cout<<sum;
cout<<endl;
cout<<endl;
cout<<endl;
return 0;
} 
void main()
{ 
 system("color 0f");
 MGraph_L G;
 int i,d,g[20][20];
 char a='a';
 d=creatMGraph_L(G);

 int s;
 char y='y';
 while(y='y')
 {
  cout<<endl;
  cout<<endl;
  cout<<endl;
  cout<<"…………………………………………………功能菜單……………………………………………"<<endl<<endl;
  cout<<endl;
  cout<<endl;
  cout<<"1、顯示該城市連接圖的鄰接矩陣……………………"<<endl;
  cout<<endl;
  cout<<endl;
  cout<<"2、最小生成樹的邊與權值和代價……………………"<<endl;
  cout<<endl;
  cout<<endl;
  cout<<endl;
  cout<<"請選擇菜單項："<<endl;
  cin>>s;
  system("cls");
  switch(s)
  {
  case 1:
   cout<<endl;
   cout<<"                        城市連接圖的鄰接矩陣顯示如下："<<endl;
   cout<<endl;
   cout<<endl;
   cout<<endl;
   cout<<endl;
   ljjzprint(G);
   break;
  case 2:
   for(i=0;i!=G.vexnum;++i)
    for(int j=0;j!=G.vexnum;++j)
     g[i+1][j+1]=G.arcs[i][j].adj;
   cout<<endl;
   cout<<"                       最小生成樹的邊與權值和代價："<<endl;
   cout<<endl;
   cout<<endl;
   prim(g,d);
   break;
  }
  cout<<endl<<"                     是否繼續？y/n:";
   cin>>y;
  if(y=='n')
   break;
  system("cls");
 }

}