#include<iostream>
#include<cstring>
#include<math.h>
#include<stdio.h>
#include<stdlib.h>
#include<conio.h>
#include<vector>
#include<queue>
#include<stack>
using namespace std;
const long long int maxWeight = RAND_MAX; //無窮大的值
const int DefaultVertices = 30;	//最大頂點數(shù)不妨設(shè)為30 
template <class T, class E>
class Graph {
protected:
    int maxVertices=10;//圖中最大頂點數(shù)
    int numVertices=0;//圖中當(dāng)前頂點數(shù)
    int numEdges=0;//圖中當(dāng)前邊數(shù)
    bool direction=false;//圖中邊的是否有方向
    bool withCost=false;//圖中的邊是否帶權(quán)
    //返回頂點名vertex的序號(從0開始)
	int getVertexPos (T vertex);	
public:   
	void DFS (const T& v)
	{
		
	} 
	
	void BFS (const T& v)
	{
	} 
                                     
    Graph(int sz , bool direct, bool cost); //構(gòu)造函數(shù)
    ~Graph()//析構(gòu)函數(shù) 
	{}	
			//析構(gòu)函數(shù)
    bool GraphEmpty () const	//判圖是否為空，因為不需要修改，因此設(shè)置為常成員函數(shù) 
    {
	  return numEdges == 0;  
	}
    bool GraphFull() const;         //判圖是否為滿
    //返回圖中當(dāng)前頂點數(shù)
   	int NumberOfVertices () 
	{ 
	   return numVertices;
	}
    //返回圖中當(dāng)前邊數(shù)
	int NumberOfEdges ()
	{ 
	 return numEdges;
	}
	//取回序號為 i 的頂點值(頂點名)
	virtual T getValue (int i){
	}
    //取頂點序號為v1,v2的邊上權(quán)值
    virtual E getWeight (int v1, int v2){
	}   
  	//取頂點 v 的第一個鄰接頂點序號
    virtual int getFirstNeighbor (int v){
	}
   //返回頂點 v 和鄰接頂點 w 的下一個鄰接頂點序號
	virtual int getNextNeighbor (int v, int w){
	}
    //插入新頂點, 點名為vertex
	virtual bool insertVertex (const T vertex){
	}
    //插入新邊(v1,v2), 權(quán)值cost
	virtual bool insertEdge (T v1, T v2, E cost){
	}
    //刪除名為 v 的頂點和所有與它相關(guān)聯(lián)的邊
	virtual bool removeVertex (T v){
	}
    //在圖中刪除邊(v1,v2)
	virtual bool removeEdge (T v1, T v2){
	}	
};


template<class T , class E>
Graph<T,E>::Graph (int sz , bool direct, bool cost)
{
	 sz = DefaultVertices,  direct=false,  cost=false;
}
//++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++


template <class T, class E> // 
class Edge_Vertices {		   //邊結(jié)點的類定義
public:
    int dest;		   //邊的鄰接(終)點序號
   	E cost;		   //邊上的權(quán)值
   	Edge_Vertices<T, E>* link;//下一個連接頂點 
	Edge_Vertices (int num=0, Edge_Vertices<T, E>* next=NULL, E weight=NULL) //構(gòu)造函數(shù)
    : dest (num), link (next), cost (weight) { }
   	bool operator != (Edge_Vertices<T, E>& R) const
	{  return dest != R.dest;  } //重載!=運算符,判邊不等
}; 



template <class T, class E> 
class Vertex {	      //頂點的類定義
public:
    T data;		      //源頂點的名字(數(shù)據(jù))
	Edge_Vertices<T, E>* next=NULL; //next指針用來連接頂點 
};

//鄰接表圖的類定義繼承圖類
template <class T, class E> 
class Graphlnk : public Graph<T, E>{
 public: 
   void Enter (void);  //輸入圖中頂點和邊信息
   void Print (void);   //輸出圖中頂點和邊信息
    //源頂點表 (各邊鏈表的源頂點)
    Vertex<T, E>* NodeTable;
    int *path;
    int *dist;
    //返回名為vertex的頂點在圖中的序號(從0開始)，
	 //若未找到，則返回-1
	int getVertexPos (const T vertx) 	//找到目標(biāo)頂點所在的序號 期中 vertx 參數(shù)為string 類型 
	{   for (int i = 0; i < this->numVertices; i++)
	        if (NodeTable[i].data == vertx) return i;
 	     return -1; 
	}             //構(gòu)造函數(shù)
    Graphlnk( int sz=DefaultVertices, bool direct=false, bool cost=false ); 
   	~Graphlnk(); //析構(gòu)函數(shù)
    T getValue (int i) { //取序號為 i 的頂點名
	    return (i >= 0 && i < this->numVertices) ? 
             NodeTable[i].data : NULL;
    }
	E getWeight (int v1, int v2);	//取邊(v1,v2)權(quán)值 
	bool insertVertex (const T& vertex); //插入名為vertex的新頂點
    bool removeVertex (int v); //刪除序號為 v 的頂點
    bool insertEdge (T in ,T out, E cost); //插入新邊
	bool removeEdge (int v1, int v2); //刪除邊(v1,v2)
    int getFirstNeighbor (int v);//取頂點v的首鄰接頂點   ###本次代碼這兩條都沒有用到 
    int getNextNeighbor (int v, int w);//取w下一鄰接點   ###本次代碼這兩條都沒有用到 
    void DFS(const T &v);
     void BFS(const T &v);
     void DFS (int v, bool visited[]);
     void BFS(int v , bool visited[]);
     void Connected_Component();
     void Dijkstra (int v );
     void Print(int v, int w);
};
// 輸出頂點 v 到頂點 w 的最短路徑
//和最短路徑長度。int* path;
// E** dist; 為類數(shù)據(jù)成員
template<typename T, typename E>
void Graphlnk<T,E>::Print(int v, int w)//輸出從V 到W 的最短路徑 
 {  //因為v和w都是 int 型,即輸入類型的下標(biāo)，因此，要用getValue 獲得原來的輸入的頂點名字 
	cout<<"始頂點 "<<this->getValue(v)<<" 到終頂點 "<<this->getValue(w)<<" 的最短路徑為:"<<endl;
	int current=w, previous;
	stack<char > Road;//定義一個char類型的棧，因為是用頂點回溯 (即從 最后的一個頂點 往前找前驅(qū)頂點的，因此我們可以用棧(后進先出的特性))
	//用棧后進先出的特性可以 在出棧的時候 按順序輸出從 開始頂點到目的頂點的  路徑 ，如果對輸出沒有要求的話就不需要棧，可以直接輸出
	//不過輸出的結(jié)果會倒置(從目的頂點 一步一步往回走 ，直到找到開始頂點) 
	stack<int >Road_Weight;//如果 頂點 要按順序輸出，還想輸出 這兩個頂點間的權(quán)值的話，那么這些權(quán)值也是倒置的，因此權(quán)值也需要利用棧的特性輸出 
	Road.push(this->getValue(w)[0]);//因為this->getValue(w) 返回的是一個string 類型， 本次測試的頂點都是要么是單個數(shù)字名字，或者單個字母名字
	// 因為是char 類型，因此只能單個字母進去，所以this->getValue(w)[0] 就是取第一個 字母/數(shù)字 
	while( current!=v )//如果這個頂點不等于 開始頂點的話 
	{
		previous=path[current];//找它的上一個頂點 
		Road.push(this->getValue(path[current])[0]);//名字入棧 
		Road_Weight.push(this->getWeight(previous,current));//權(quán)值入棧 
		current=previous; 
	}
	string  p;//string 變量 p 用來記錄前面的頂點和 做臨時變量 
	string  e;//string 變量 e 用來輸出頂點名字 
	int q;
	int x=1;//一個標(biāo)志 
	int i = 1;//第i步 
	while(Road.empty()!=true)
	{  
	//這個if 語句只運行一次，為什么呢，考慮到 奇數(shù)個頂點的話，那么，最短路徑至少有兩個頂點，如果第一次就把頂點輸出完了
	//那么后面的if語句都不會運行了，但是如果 是奇數(shù)個頂點呢？ 奇數(shù)個頂點的話，程序編譯不會出錯，但是運行會中斷， 即棧已經(jīng)空了，不能彈棧了
	//因此，執(zhí)行一次這個if語句 就開始 對頂點一個 一個的彈棧，而不是 兩個兩個的彈 
	   if(x)
	   {
	   p=Road.top();
	   Road.pop();
	   q=Road_Weight.top();
	   Road_Weight.pop();
	      e=Road.top();
	   Road.pop();
	   x=0;//讓if 語句為假 
	    cout<<"第"<<i++<<"步為:  "<<"頂點"<<p<<"-->到頂點"<<e<<"  長度為: "<<q<<endl;
	
		}
	
	 
	   if(Road.empty()!=true)//如果棧不為空 
	   {
	   	p=e;//因為這個p在后面不再 用來接收 棧彈出的頂點，而是充當(dāng)一個臨時變量-------用上一個頂點 的末頂點 進行覆蓋 
	   e=Road.top();//取棧首頂點 
	   Road.pop();// 彈棧 
	    q=Road_Weight.top();//取棧里的首權(quán)值 
	   Road_Weight.pop();
	   cout<<"第"<<i++<<"步為:  "<<"頂點"<<p<<"-->到頂點"<<e<<"  長度為: "<<q<<endl;	
	   }
	   
	}
	cout<<"最短路徑總長度為："<<dist[w]<<endl;//輸出最短路徑長度 
}

template<class T,class E>
//Graphlnk是一個帶權(quán)有向圖.數(shù)據(jù)成員E dist[v][j],
//0≤j<n, 是當(dāng)前求到的從頂點v到 j的最短路 徑長度,
//int path[v][j],0≤j<n, 存放求到的最短路徑
void Graphlnk<T,E>::Dijkstra (int v  )//Dijkstra算法，求得圖任意兩點間的 最短路徑 
{ 	int k;//變量k 
	bool *s = new bool[this->numVertices];//并查集s，標(biāo)記頂點是否已經(jīng)在最短路徑的頂點集里 
	this->path=new int [this->numVertices];//路徑數(shù)組(跳躍式，要用回溯才能找出整個完整的路徑) 
	this->dist= new int [this->numVertices];//源點v到任意頂點vi的最短路徑數(shù)組， 
	for(int i = 0 ; i < this->numVertices;i++)//初始化 
	{	
		s[i]=false;//把所有的頂點都標(biāo)記為:未在最短路徑頂點集 
		if(this->getWeight(v,i)!=maxWeight)//如果有v和vi間如果有權(quán)值的話，那么，就是說，這兩點是連通的。 
		// 既然兩點是連通的，那么，這個路徑就有可能是最短的。 
		this->dist[i]=this->getWeight(v,i);
		else //否則？就是沒有連通咯，就用maxWeight賦值給他，即：如果dist[i]==maxWeight那么 就判定為兩點是不連通的 
		dist[i]=maxWeight;	
		if(this->dist[i]<maxWeight||v==i)//如果有邊連通，或者i==v 
		this->path[i]=v;//就讓i這個頂點的前驅(qū) 是v (如果v==i 就讓自己指向自己) 
		else 
		path[i]=-1;// 否則vi和 v 沒有路，即兩點間不連通  
	}
	dist[v]=0;//首先，規(guī)定，v->v 即自己到自己的距離是0 
	s[v]=true;//將開始頂點v放入并查集數(shù)組中 
	int min;//最小路徑的一個值 
	for(int i = 1; i <this->numVertices;i++)
	{
		 min = maxWeight;//首先要讓這個最小值足夠大，然后后面的那些路徑權(quán)值才會比這個值小然后把它替換為真正的"最小值" 
		for(int j=0;j<this->numVertices;j++)
		if(!s[j]&&dist[j]<min)//如果這個頂點沒有在最小路徑的頂點集里面，則判定是否連通
		//如果連通的話，就從這些 連通的頂點間找到一組最小的連通 頂點。 
		{
			k=j;
			min=dist[j];
		}
		s[k]=true;//找一個：若在原來路徑上 添加一個頂點，首先，這個頂點在最短路徑頂點集和之外， 其次，這個頂點沿著其余頂點回到開始頂點路徑最短 
		for(int w = 0 ; w <this->numVertices;w++)
		//從這個新加入的頂點Vnew出發(fā)，不斷的去找和它相連接的頂點vi(i取任意正整數(shù)，即頂點可能不知有一個，可能是多個)
		//然后看v到vi的路徑短一點還是,v到Vnew再到Vi,如果是v到Vnew 再到vi 比 直接從v到vi更短的話，那么就替換 v到Vw的最小距離dist[w]
		//并且規(guī)定w的前驅(qū)頂點為k ,即:path[w]=k; (此時w還沒有在最短路徑頂點集合里面) 
		//由此我們可以知道：既然每加入一個 頂點到 最短路徑頂點集里面，都會執(zhí)行這段代碼。 
		//然后 都會從剛加入的那個頂點去 找遍所有 和它關(guān)聯(lián)的頂點，所以，如果說這個加入的頂點如果 和目的頂點X相連，那么加入這個頂點后
		// 執(zhí)行下面的代碼，就可以求出當(dāng)前從始頂點到目的頂點X的最短路徑,為什么是當(dāng)前？因為這個最小是當(dāng)前最小的，因為還有其他頂點未加入頂點集
		//即有可能從 v出發(fā) 經(jīng)過某個 未加入  最短路徑頂點集合里的頂點 再到X 的路徑大小 比 從v到原先那個加入  最短路徑頂點集合里的頂點 再到x 的路徑要小
		//所以，下面的代碼每次執(zhí)行都會求得 一個臨時的最短路徑，如果頂點都加入完了，那么，自然是最短路徑了  
		if(!s[w]&&dist[w]>(dist[k]+this->getWeight(k,w))&&this->getWeight(k,w)!=-1)
		{
			dist[w]=dist[k]+this->getWeight(k,w);// 
			path[w]=k;//讓w頂點的前驅(qū)是k 
		}
		
	}
	delete []s ;//刪除標(biāo)記數(shù)組
	//輸出代碼可以在函數(shù)體里，也可以 加一個print函數(shù) 在函數(shù)體外 
//	cout<<"始頂點 "<<v<<" 到終頂點 "<<w<<" 的最短路徑為：終頂點 "<< w;
//	int current=w, previous;
//	while( current!=v )
//	{
//		previous=path[current];
//		cout<<"路徑"<<path[current];
//		cout<<"最小距離"<<dist[current];
//		cout<<" <-權(quán)值[ "<<getWeight(previous,current)<<" ]-頂點 "<<previous;
//		current=previous;
//	}
//	cout<<"。最短路徑總長度為："<<dist[w]<<endl;
}

template<class T, class E>
void Graphlnk<T,E>::Connected_Component()//分別輸出連通分量 和輸出有向圖中連通分量的個數(shù) 
{	int Connected_Component_numbers=0;
	bool visited[this->numVertices];
	for(int i = 0 ; i <this->numVertices;i++)
		visited[i]=false;//初始化這個visited 數(shù)組
	for(int i =0; i < this->numVertices;i++)
	{
	if(!visited[i])//如果這個結(jié)點沒有被訪問過
	{
		cout<<"從"<<this->getValue(i)<<"開始的連通分量為:";
		this->DFS(i,visited);
		cout<<endl;
		Connected_Component_numbers+=1;
	 }
	}
	if(this->direction==true)
	cout<<"此有向圖的連通分量為:"<<Connected_Component_numbers<<endl;
	else 
	cout<<"此無向圖的連通分量為:"<<Connected_Component_numbers<<endl;
	 delete [] visited;//結(jié)束后刪除數(shù)組	
}
//從名為 v 的頂點出發(fā)廣度優(yōu)先遍歷
template <class T, class E> 
void Graphlnk<T,E>::BFS(const T& v)
{    int i, w; 
      //創(chuàng)建訪問標(biāo)記數(shù)組
     bool* visited = new bool[this->numVertices];
      //對圖中所有頂點初始化訪問數(shù)組visited
     for (i = 0; i < this->numVertices; i++)
          visited[i] = false; //初始化為都未訪問過
    int loc = getVertexPos (v); //取名為 v 的頂點序號
    if(loc == -1) //名為 v 的頂點未找到
        cout<<"頂點 "<<v<<"沒有找到，廣度優(yōu)先遍歷失敗。";
     else
     {
        cout << getValue (loc) << ' '; //訪問頂點 v
        visited[loc] = true; //標(biāo)記頂點 v 已訪問過
        //頂點 v 進隊列, 實現(xiàn)分層訪問
        queue<int> q; 
		 q.push(loc); //訪問過的頂點進隊列 
        while (!q.empty() ) //循環(huán), 訪問所有結(jié)點
        {	loc = q.front();//記錄當(dāng)前隊列第一個頂點的值 
             q.pop(); // 然后記錄完讓它出隊列 
             w = getFirstNeighbor (loc); //取它的第一個鄰接頂點 
            while (w != -1)  //當(dāng)鄰接頂點w存在
            {   if (!visited[w]) //如果未訪問過
                 {   cout << getValue (w) << ' ';//訪問它然后輸出它 
                      visited[w] = true;	//標(biāo)記此頂點已經(jīng)訪問過
                      q.push(w); 	//頂點w進隊列
                 }
                 w = getNextNeighbor (loc, w); //取下一個鄰接頂點 
            }
            
        } //外層循環(huán)，判隊列空否
    }
    delete [] visited;
}

template<class T , class E >
void Graphlnk<T,E>::DFS(const T &v)
{
	int sign;
	bool *visited = new bool[this->numVertices];
	for(int i = 0; i <this->numVertices;i++)
	{
		visited[i]=false;//初始化都為為訪問過 
	}
	sign=this->getVertexPos(v);
	if(sign==-1)
	cout<<"頂點"<<v<<"不存在"<<"深度優(yōu)先遍歷失敗"<<endl;
	else //否則為存在
	DFS(sign,visited);
	delete[] visited; //深度優(yōu)先遍歷完成的話，就刪除這個數(shù)組 
}
template<class T,class E>
void Graphlnk<T,E>::DFS(int v , bool visited[])
{
	cout<<this->getValue(v)<<" ";
	visited[v]=true;
	int w = this->getFirstNeighbor(v);
	while(w!=-1)
	{
		if(!visited[w])//如果沒有訪問過為真 
		DFS(w,visited);
		w=this->getNextNeighbor(v,w);//否則回退 然后繼續(xù)搜索 
	}
}


template<class T,class E>
bool Graphlnk<T,E>::removeEdge (int v1, int v2)//刪除邊這個比較簡單 
{	
		if(v1<0||v2<0||v1>this->numVertices||v2>this->numVertices)//這種情況就是不符合，不符合就返回false  
		return false ;
		else //否則為符合的 
		{
		
	Edge_Vertices<T,E> *temp;//這是一個中間變量 
	temp=this->NodeTable[v1].next;//讓它先等于頂點表個的下一個 
	while(temp)
	{		
		if(temp->dest==v2)//如果一開始就是等于要刪除的那個頂點的話(可能會有誤解哦，這里不是刪除邊么，怎么刪除頂點？)
		//因為刪除末頂點的話，就會少掉一條邊 
		{
			if(temp->link==NULL)//如果這條鏈只有這個待刪除的頂點 
			{
				this->NodeTable[v1].next=NULL;//讓頂點表的那個頂點的下一個頂點指向空 
				delete temp;	//刪除這個頂點 
				break;//跳出循環(huán) 
			}
			else{ //如果不為空的話 
		 	this->NodeTable[v1].next = temp->link;//讓頂點表的下一個頂點指向 待刪除 目標(biāo)頂點的下一個 
		 	delete temp;//刪除結(jié)點 
		 	break;
		 }
		}	if(temp)//防止內(nèi)存訪問出錯 
		if(temp->link->dest ==v2)//不是第一個頂點是要刪除的頂點  這個if 語句記作 AAAAA  
		{	Edge_Vertices<T,E> *temp2;//定義一個中間變量temp2 
			temp2=temp->link;//讓temp  2指向 待刪除 目標(biāo)定點 
			temp->link=temp->link->link;//利用temp 斷開 目標(biāo)定點 與 子鏈的連接 
			delete temp2;//刪除目標(biāo)頂點 
			break;//跳出循環(huán) 
		}	if(temp)//防止內(nèi)存訪問出錯 
	 		temp=temp->link;//根據(jù)這條語句，會回到剛才 AAAAA 那個 if語句 
	}
	//要考慮有向圖和無向圖哦
	if(this->direction==false)//如果是無向圖的話 
	{
	     temp=this->NodeTable[v2].next;
	while(temp)
	{			//此段代碼與上面的邏輯完全相同，不再贅述 
		if(temp->dest==v1)
		{
			if(temp->link==NULL)
			{
				this->NodeTable[v2].next=NULL;
				delete temp;
				break;	
			}
			else{ 
		 	this->NodeTable[v2].next = temp->link;
		 	delete temp;
		 	break;
		 }
		}
		if(temp)
		if(temp->link->dest ==v1)
		{	Edge_Vertices<T,E> *temp2;
			temp2=temp->link;
			temp->link=temp->link->link;
			delete temp2;
			break;
		}	if(temp)
	 		temp=temp->link;
	}
	 
   }
}
this->numEdges--;//記得刪完 邊數(shù)要 -1; 
return true;//刪除成功返回true  
}


template<class T , class E >
bool Graphlnk<T,E>::removeVertex (int v) //刪除序號為 v 的頂點
{
    if(v<0||v>=this->numVertices)//如果下標(biāo)不符合規(guī)定 
	return false;
	else //否則為符合 
	{
	
	int del_vex_num=v;//記錄這個刪除的下標(biāo) 
	if(v!=this->numVertices-1)//如果不是刪除最后一個頂點的話 
	this->NodeTable[v]=this->NodeTable[--this->numVertices];//就用最后一個頂點頂?shù)哪菞l"鏈"替代這個待刪除頂點的"鏈" 
	//如果刪除的是最后一個頂點的話，自然就沒有影響了 
	else 
{
		this->numVertices--;
	int end_edg=0;//因為如果直接刪掉這個點的話，那么這個點關(guān)聯(lián)的邊也要減掉
	Edge_Vertices<T,E> *p;
	p=this->NodeTable[v].next;
	while(p)
	{	
		if(p)
		{  end_edg++;//如果有一個頂點，且不為空的話，那么涉及的邊數(shù)就+1 
		 } 
		 p=p->link;
	 } 
	 this->numEdges-=end_edg;
}
	for(int i= 0 ; i < this->numVertices;i++)//此時的numVertices已經(jīng)-1 ，然后對這所有的鏈進行操作，如果有將要刪除頂點與這個頂點相連，則刪除 
	{	Edge_Vertices<T,E> *temp;
		temp=this->NodeTable[i].next;
		//第一種情況：第一個連接的 頂點就是 將要刪除的那個頂點
		//這種情況很好做
		if(temp->dest ==v)
		{
			if(temp->link==NULL)//如果這條鏈只有一個結(jié)點，然后第一個結(jié)點恰好是這個將要刪除的頂點的話 
			{ 
				this->NodeTable[i].next=NULL;//這樣的話，直接刪掉它	
				this->numEdges--;
			}
			else //否則
			 {
			 this->NodeTable[i].next=temp->link;
			 delete temp;//刪除臨時的指針變量 
			 this->numEdges--;
			}
		 } 
		 else //第二種情況，就需要循環(huán)了，因為每一個頂點最多只有一個 將要刪除的那個頂點的下標(biāo) 
		 {//第一個結(jié)點的dest!=v 
		 	while(temp)
			 {
			 	if(temp->link)
				 {
				 
			 	if(temp->link->dest==v)//第一個的下一個頂點剛好是 這個dest 的話  
			 	{
			 		Edge_Vertices<T,E> *temp2;
			 		temp2=temp->link;//中間變量temp2; 
			 	  	temp->link=temp->link->link;//斷開這個將要刪除的頂點
					delete temp2;//刪除剛才的中間變量// 
					this->numEdges--;
					break;
				 } 
				}
				 temp=temp->link;//這個最終會變成NULL,最后跳出循環(huán); 
			  } 
		 }
	}
	if(v!=this->numVertices)//如果這個待刪除的下標(biāo)不等于 最后那個頂點的話 ，因為頂點 調(diào)動 位置，所以需要改變 鏈中頂點下標(biāo)名字 
	for(int i = 0 ; i < this->numVertices;i++)
	{		Edge_Vertices<T,E> *temp;
		temp=this->NodeTable[i].next;
		while(temp)
		{  
			if(temp)
			if(temp->dest==this->numVertices)//就是說，最后的那個頂點要去前面 替換掉 剛才刪除的那個頂點的位置 ，因此，下標(biāo)也要改 
			{
				temp->dest=v;// 循環(huán)遍歷 出最后頂點的dest  然后用v  替換  
				break;
			}
			temp=temp->link;//移動 
		}
	}
	}//第一個else 的右括號 
	return true;//刪除頂點成功 
}
template<class T , class E>
	E Graphlnk<T,E>::getWeight (int v1, int v2)//獲得兩個點之間的權(quán)值 
	{
		if(v1<this->numVertices&&v2<this->numVertices&&v1!=v2)
		{  
	//		 string a = this->NodeTable[v2].data;
			 Edge_Vertices<T,E> *temp;
			 temp=this->NodeTable[v1].next;//從v1這條鏈找一個點開始 
			while(temp)//然后循環(huán)，直到找到v2 
			{
			  if(temp->dest==v2)//找到了直接返回它的權(quán)值 
			  return temp->cost;
			  else 
			  temp=temp->link;	//沒找到，移動 
			}
			return maxWeight;
			
		}
	}




template<class T , class E >
bool Graphlnk<T,E>::insertVertex (const T& vertex)//插入頂點 ，插在之前定義的那個頂點表那里 
{
	if(this->numVertices<this->maxVertices)//如果圖當(dāng)前的頂點數(shù)小于 允許插入的最大頂點數(shù)，則可以插入 
	{
		this->NodeTable[this->numVertices++].data=vertex;
		
	}
}
template<typename T, typename E>
bool Graphlnk<T,E>::insertEdge(T in, T out, E cost)//插入邊 
{   int  v1= getVertexPos(in); //這里還是直接是輸入定點名，用函數(shù)找這個頂點的下標(biāo) 
    int v2=getVertexPos(out);
	if(v1>-1 && v1<this->numVertices && v2>-1 && v2 < this->numVertices )//這兩個下標(biāo)都在頂點表里
	{     //將新邊的權(quán)值插入邊鄰接矩陣的第v1行,v2列,利用頭插法
	     Edge_Vertices<T,E> *temp =new Edge_Vertices<T,E>; //生成一個邊結(jié)點。
		 temp->dest=v2;// 記錄這個點的值 
		 temp->link=this->NodeTable[v1].next;//將它插在 v1 這個頂點的這條鏈里 ，這里采用頭插法 (temp 街上NodeTable[v1]的后面 一大串(當(dāng)然一開始為空))
		 //比如這一大串為ABCDE  然后temp  接上去就為 temp->ABCDE; 
		 if(this->withCost==true)//如果需要記錄權(quán)值 
		 temp->cost=cost;// 記錄 
		 this->NodeTable[v1].next =temp;// 吧temp接上去 head ->temp->ABCDE;
		 
		 
		 if(this->direction==false)//如果是無向圖的話，還要從v2那條鏈 接上 v1  
		  {
		  Edge_Vertices<T,E> *temp2=new Edge_Vertices<T,E> ;
		  temp2->dest=v1;
		  temp2->link=this->NodeTable[v2].next;
			if(this->withCost==true)
			 temp2->cost=cost;//同樣的是采用頭插法，不再一一贅述 
			this->NodeTable[v2].next=temp2;
		} 
		this->numEdges++;
	return true;
	}
	else return false; //插入新邊失敗(不滿足if 語句)
}
//構(gòu)造函數(shù)建立鄰接表
template <class T, class E>
Graphlnk<T, E>::Graphlnk (int sz,bool direct, bool cost):Graph<T,E>(sz, direct, cost)
{	//創(chuàng)建源點表數(shù)組
   NodeTable = new Vertex<T, E>[this->maxVertices];//分10個Vertex結(jié)點大小 的指針 數(shù)組 
    if (NodeTable == NULL) 
    {
	 cerr << "內(nèi)存分配出錯！" << endl;  exit(1); 
	}
    for (int i = 0; i < this->maxVertices; i++)  
        NodeTable[i].next= NULL;//對NodeTable的指針進行初始化 
}
//析構(gòu)函數(shù)：刪除一個鄰接表
template <class T, class E>
Graphlnk<T, E>::~Graphlnk()
 {	
   for (int vertex = 0; vertex < this->numVertices; vertex++ ){
        //current指向源點vertex邊鏈表的第1個鄰接點
	    Edge_Vertices<T, E> * current = NodeTable[vertex].next;
        while (current != NULL) {//鄰接點存在
            NodeTable[vertex].next = current->link; //脫鏈
            delete current; //釋放邊鏈表的第1個鄰接點
            // current重新指向邊鏈表的第1個鄰接點
            current = NodeTable[vertex].next;
        }
   	} 
   	delete []NodeTable; //刪除源點表數(shù)組
}
//返回序號為 v 的源點第1個鄰接點的序號(從0開始), 
//若未找到鄰接點, 則返回-1
template <class T, class E>
int Graphlnk<T, E>::getFirstNeighbor (int v)
{   if (v != -1) //源點v存在
	 {  //current指向源點v的邊鏈表第1個鄰接點
         Edge_Vertices<T, E>* current = NodeTable[v].next;
	     if (current != NULL)//頂點v的第1個鄰接點存在
            //返回第1個鄰接點的序號
            return current ->dest;
   	}
   	return -1; //不存在第1個鄰接點，返回-1
}
//返回源點v和鄰接點w的下1個鄰接點的序號，
//若未找到下1個鄰接點, 則返回-1
template <class T, class E>
int Graphlnk<T, E>::getNextNeighbor (int v, int w)
{  if (v != -1) { //源頂點 v 存在
        Edge_Vertices<T, E>* current = NodeTable[v].next;//終頂點current 
        while (current != NULL && current->dest != w)
             current = current->link; //先找到終頂點 w
	    if (current != NULL && current->link != NULL) 
	        //返回w的下1個鄰接頂點序號
            return current->link->dest;
   	}
   	return -1; //未找到下1個鄰接頂點，返回-1
}
template <class T, class E>
void Graphlnk<T,E>::Enter()
{	int Count,vertexs,Edges;
	T e1,e2;
	cout<<"圖中共有多少個頂點？";
	cin>>vertexs;
	cout<<"輸入圖中共 "<<vertexs<<" 個頂點名：";
    //輸入圖中全部頂點名
	for(Count=0;Count<vertexs;Count++)
	{	cin>>e1;
		insertVertex(e1);
	}
	E weight;
	char Answer;
	cout<<"圖形的邊有方向嗎(y/n)?";
	cin>>Answer;
	if(Answer=='y' || Answer=='Y')
		this->direction=true;
	else
		this->direction=false;
cout<<"圖中的邊帶權(quán)嗎(y/n)?";
	cin>>Answer;
	if(Answer=='y' || Answer=='Y')
		this->withCost=true;
	else
		this->withCost=false;
	cout<<"圖中共有多少條邊？";
	cin>>Edges;
	Count=0;
while(Count<Edges)
	{
		cout<<"輸入第 "<<Count+1<<" 條邊的2個頂點名和權(quán)值：";
		cin>>e1>>e2>>weight;
		if(insertEdge(e1,e2,weight)) 
		      Count++;
		else
                cout<<"頂點名有誤，重新輸入這條邊！"<<endl;
	}
}
// 輸出圖中所有頂點和邊的信息
template <class T, class E>
void Graphlnk<T, E>::Print(void)
{	int row,column;
	E weight;
	cout<<"圖中共有 "<<this->numVertices<<" 個頂點和 "<<this->numEdges<<" 條邊："<<endl;

	
for(row=0;row<this->numVertices;row++)
	{
		//按行號取出序號為row的頂點名并輸出
		cout<<"序號"<<row<<"源點"<<"["<<getValue(row)<<"]"<<"->";
		Edge_Vertices<T, E> *temp;
		temp=this->NodeTable[row].next;
		if(temp)//可能它的下一個頂點直接就是空 
		{
		
		while(temp->link)
		{
			cout<<"["<<"鄰接點"<<temp->dest<<"]";
			if(this->withCost)
			cout<<"["<<"權(quán)值"<<temp->cost<<"]";
			cout<<"[-]->" ;
		temp=temp->link;
		
		}
		cout<<"["<<"鄰接點"<<temp->dest<<"]";
		if(this->withCost)
			cout<<"["<<"權(quán)值"<<temp->cost<<"]";
			cout<<"[^]" ;
	cout<<endl;
		}
		else 
		cout<<"[^]"<<endl;
}

}

int main()
{	
	Graphlnk<string,double> graph;
	graph.Enter();
	graph.Print();
//	string del;
//	cout<<"請輸入你想要刪除的一個頂點"<<endl;
//	cin>>del;
// 	int index= graph.getVertexPos(del);
//	if(graph.removeVertex (index))
//	cout<<"刪除成功"<<endl;
//	else 
//	cout<<"刪除失敗";
//	graph.Print();
//	cout<<"請輸入你想要刪除那條邊的兩個頂點"<<endl;
//	string one ,two;
//	cin>>one>>two;
//	int num_one,num_two;
//	num_one=graph.getVertexPos(one);
//	num_two=graph.getVertexPos(two);
//	if(graph.removeEdge(num_one,num_two))
//	cout<<"刪除成功"<<endl;
//	else 
//	cout<<"刪除失敗"<<endl; 
//	graph.Print();
//cout<<"請輸入一個頂點來進行深度優(yōu)先遍歷"<<endl;
// string dfs;
// cin>>dfs;
// graph.DFS(dfs);
// cout<<endl; 
//cout<<"請輸入一個頂點來進行廣度優(yōu)先遍歷"<<endl;
//string bfs;
//cin>>bfs;
//graph.BFS(bfs);
//cout<<endl;
//graph.Connected_Component();
	string  a,b;
	cout<<"輸入求最短路徑的始頂點：";cin>>a;
	int v = graph.getVertexPos(a);
	cout<<"輸入求最短路徑的終頂點：";cin>>b;
	int w = graph.getVertexPos(b);
	graph.Dijkstra(v);
	graph.Print(v,w);
//system("PAUSE");
}