#include<iostream>
#include <string>                  //引入標(biāo)準(zhǔn)庫中的頭文件
#include "graph.h"                //引入頭文件
using namespace std;


/*   
 *前置條件：圖不存在
 *輸    入：無 
 *功    能：圖的初始化
 *輸    出：無
 *后置條件：構(gòu)造一個空的圖
 */
template <class T>
MGraph<T>::MGraph(T a[], int n, int e) 
{
 vertexNum=n;                 //頂點(diǎn)數(shù)
 arcNum=e;                    //邊數(shù)
 int i,j,k;
for (i=0; i<vertexNum; i++) 
  vertex[i]=a[i];
 for (i=0; i<vertexNum; i++)    //初始化鄰接矩陣
	 for (j=0; j<vertexNum; j++)
     arc[i][j]=0;             
   for (k=0; k<arcNum; k++)   //依次輸入每一條邊，并修改鄰接矩陣的相應(yīng)元素
	   {
cin>>i>>j;                    //邊依附的兩個頂點(diǎn)的序號
arc[i][j]=1;                  //置有邊標(biāo)志
arc[j][i]=1;    
       }
}

/*   
 *前置條件：圖已存在
 *輸    入：無
 *功    能：輸出圖中所有頂點(diǎn)的數(shù)據(jù)信息
 *輸    出：圖中所有頂點(diǎn)的數(shù)據(jù)信息
 *后置條件：圖保持不變
 */
template <class T>
void MGraph<T>::PutVex( )           //取所有頂點(diǎn)            
{                                   //假設(shè)源點(diǎn)是第0個頂點(diǎn)，即頂點(diǎn)序號是0
	int i=0;
    for(i=0;i<vertexNum;i++)
	   {                            //輸出圖中所有的頂點(diǎn)
          cout<<vertex[i]<<"\n";
	   }
}
/*   
 *前置條件：圖已存在
 *輸入：頂點(diǎn)i
 *功能：輸出圖中頂點(diǎn)i的數(shù)據(jù)信息
 *輸出：圖中頂點(diǎn)i的數(shù)據(jù)信息
 *后置條件：圖保持不變
 */
template <class T>
void MGraph<T>::GetVex(int i,T v[MaxSize])      //取頂點(diǎn)i             
{                                               //假設(shè)源點(diǎn)是第0個頂點(diǎn)，即頂點(diǎn)序號是0
	v[i]=vertex[i];
    if (i>vertexNum) throw "位置";              //頂點(diǎn)i不存在則拋出異常
	else
		cout<<v[i]<<"\n";                       //返回頂點(diǎn)i	
}

/*  
 *前置條件：圖已存在
 *輸    入：頂點(diǎn)name,位置num
 *功    能：在圖中num位置插入一個頂點(diǎn)name 
 *輸    出：如果插入不成功，拋出異常
 *后置條件：如果插入成功，圖中增加了一個頂點(diǎn)
 */
template <class T>
void MGraph<T>::InsertVex(int num,T name)        //在圖中插入一個頂點(diǎn)，其編號為i，值為value
{                                                //假設(shè)源點(diǎn)是第0個頂點(diǎn)，即頂點(diǎn)序號是0
 if ( num<0|| num>vertexNum) throw "位置";       //如果num輸入不正確拋出異常
 int row;                                        //行
 int col;                                        //列
 int numv;                                       //最后一個頂點(diǎn)所在的位置
	 numv = vertexNum-1;
 if(num>-1)                                      //num存在
  vertexNum++;                                   //頂點(diǎn)數(shù)加1
for(int i=numv;i>num-1;i--)                      //i從最后一個頂點(diǎn)的下一個位置開始循環(huán)
	vertex[i]=vertex[i-1];                       //把從num位置的頂點(diǎn)到最后一個頂點(diǎn)均向后移一位
	vertex[num]=name;                            //把要插入的頂點(diǎn)的值放在num位置上
 for(row=numv;row>=0;row--)                      //把從num列到最后一列的元素均向下移一列
  {
    for(col=numv;col>=num;col--)
		  arc[row][col+1]=arc[row][col];
     arc[row][num]=10000;
  }
  for(row=numv;row>=num;row--)                   //把從num行到最后一行的元素均向下移一行
	  for(col=0;col<=numv+1;col++)
		  arc[row+1][col]=arc[row][col];		
for(col=0;col<vertexNum;col++)
		  arc[num][col]=10000;                   //把num位置所在的行、列的值均置為無窮大
  
 }
/*   
 *前置條件：圖已存在
 *輸    入：頂點(diǎn)pos 
 *功    能：在圖中刪除頂點(diǎn)pos 
 *輸    出：如果刪除不成功，拋出異常
 *后置條件：如果刪除成功，圖中減少了一個頂點(diǎn),相應(yīng)頂點(diǎn)所建立的邊也消去
 */
template <class T>
void MGraph<T>::DeleteVex(int pos)              //刪除第pos個頂點(diǎn)
{                                               //假設(shè)源點(diǎn)是第0個頂點(diǎn)，即頂點(diǎn)序號是0
 if ( pos<0||  pos>MaxSize) throw "位置";       //如果pos輸入不正確拋出異常
 int row;                                       //行
 int col;                                       //列
 int numv=vertexNum;                            //numv等于頂點(diǎn)數(shù)
  if(pos>-1){                                    //pos存在 
   for(int i=pos;i<numv-1;i++)
   vertex[i]=vertex[i+1];                       //把從pos到最后的每個點(diǎn)的位置依次向前移一位
   vertexNum--;                                 //頂點(diǎn)數(shù)減1
   for(row=0;row<numv;row++)
   {
     for(col=pos;col<numv;col++)
		  arc[row][col]=arc[row][col+1];        //把從pos列到最后一列的元素均向前移一列
     arc[row][numv-1]=10000;                    //把pos所在的列上的值置為無窮大
   }
   for(row=pos;row<numv;row++) 
	  for(col=0;col<numv;col++)
		  arc[row][col]=arc[row+1][col];        //把從pos行到最后一行的元素均向上移一行
  } 
}
/*   
 *前置條件：圖已存在
 *輸    入：頂點(diǎn)n、w 
 *功    能：在圖中刪除頂點(diǎn)n、w 依附的邊 
 *輸    出：如果刪除不成功，拋出異常
 *后置條件：如果刪除成功，圖中減少了一條邊
 */
template <class T>
void MGraph<T>::DeleteArc(int n, int w)        //在圖中刪除一條邊，其依附的兩個頂點(diǎn)的編號為i和j
{
 if ( n>MaxSize||  w>MaxSize) throw "位置";    //如果輸入不正確拋出異常
	 arc[n][w]=arc[w][n]=10000;   
}
/*   
 *前置條件：圖已存在
 *輸    入：頂點(diǎn)i、j
 *功    能：在圖中插入頂點(diǎn)i、j及其所依附的邊 
 *輸    出：如果插入不成功，拋出異常
 *后置條件：如果插入成功，圖中增加了一條邊
 */
template <class T>
void MGraph<T>::InsertArc(int i, int j,int n)   //在圖中插入一條邊，其依附的兩個頂點(diǎn)的編號為i和j
{
  if ( i>MaxSize||  j>MaxSize) throw "位置";   //如果輸入不正確拋出異常	
  arc[i][j]=n;
  arc[j][i]=n;
  cout<<"從"<<vertex[i]<<"到"<<vertex[j]<<"的路徑長度為："<<arc[i][j]<<"\n"; //輸出插入的兩頂點(diǎn)之間的路徑
} 
/*   
 *前置條件：圖已存在
 *輸    入：遍歷的起始頂點(diǎn)v
 *功    能：從頂點(diǎn)v出發(fā)深度優(yōu)先遍歷圖
 *輸    出：圖中頂點(diǎn)的一個線性排列
 *后置條件：圖保持不變
 */   
int visited[MaxSize];
template <class T>
void MGraph<T>::DFSTraverse(int v)     //深度優(yōu)先遍歷圖
{
	
	if ( v>vertexNum) throw "位置";   //如果輸入不正確拋出異常
     cout<<vertex[v]<<" ";
	  visited[v]=1;                    //已訪問v頂點(diǎn)	  
      for (int j=0; j<vertexNum; j++)
	  {
		 if (arc[v][j]<10000 && visited[j]==0)
	       DFSTraverse(j); 
	  }	 
}     

/*   
 *前置條件：圖已存在
 *輸    入：遍歷的起始頂點(diǎn)v
 *功    能：從頂點(diǎn)v出發(fā)廣度優(yōu)先遍歷圖
 *輸    出：圖中頂點(diǎn)的一個線性排列
 *后置條件：圖保持不變
 */ 
int visited2[MaxSize];
template <class T>
void MGraph<T>::BFSTraverse(int v)     //廣度優(yōu)先遍歷圖
{
 //
  if ( v>vertexNum) throw "位置";      //如果輸入不正確拋出異常
  int front=-1;
  int rear=-1;                         //初始化隊(duì)列,假設(shè)隊(duì)列采用順序存儲且不會發(fā)生溢出
  cout<<vertex[v]<<" ";                //被訪問頂點(diǎn)入隊(duì)
  visited2[v]=1;  
  int Q[MaxSize];
  Q[++rear]=v; 
  while (front!=rear)
  {
     v=Q[++front];                     //將隊(duì)頭元素出隊(duì)并送到v中
     for (int j=0; j<vertexNum; j++)
       if (arc[v][j]<10000 && visited2[j]==0 ){
          cout<<vertex[j]<<" ";
		  visited2[j]=1; 
		  Q[++rear]=j;
       }
  }
}