#include<iostream>
#include <string>                  //引入標準庫中的頭文件
#include "graph.h"                //引入頭文件
using namespace std;


/*   
 *前置條件：圖不存在
 *輸    入：無 
 *功    能：圖的初始化
 *輸    出：無
 *后置條件：構造一個空的圖
 */
template <class T>
MGraph<T>::MGraph(T a[], int n, int e) 
{
 vertexNum=n;                 //頂點數
 arcNum=e;                    //邊數
 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++)   //依次輸入每一條邊，并修改鄰接矩陣的相應元素
	   {
cin>>i>>j;                    //邊依附的兩個頂點的序號
arc[i][j]=1;                  //置有邊標志
arc[j][i]=1;    
       }
}

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

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

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