#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;	//最大頂點(diǎn)數(shù)不妨設(shè)為30 
template <class T, class E>
class Graph {
protected:
    int maxVertices=10;//圖中最大頂點(diǎn)數(shù)
    int numVertices=0;//圖中當(dāng)前頂點(diǎn)數(shù)
    int numEdges=0;//圖中當(dāng)前邊數(shù)
    bool direction=false;//圖中邊的是否有方向
    bool withCost=false;//圖中的邊是否帶權(quán)
    //返回頂點(diǎn)名vertex的序號(hào)(從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	//判圖是否為空，因?yàn)椴恍枰薷?，因此設(shè)置為常成員函數(shù) 
    {
	  return numEdges == 0;  
	}
    bool GraphFull() const;         //判圖是否為滿
    //返回圖中當(dāng)前頂點(diǎn)數(shù)
   	int NumberOfVertices () 
	{ 
	   return numVertices;
	}
    //返回圖中當(dāng)前邊數(shù)
	int NumberOfEdges ()
	{ 
	 return numEdges;
	}
	//取回序號(hào)為 i 的頂點(diǎn)值(頂點(diǎn)名)
	virtual T getValue (int i){
	}
    //取頂點(diǎn)序號(hào)為v1,v2的邊上權(quán)值
    virtual E getWeight (int v1, int v2){
	}   
  	//取頂點(diǎn) v 的第一個(gè)鄰接頂點(diǎn)序號(hào)
    virtual int getFirstNeighbor (int v){
	}
   //返回頂點(diǎn) v 和鄰接頂點(diǎn) w 的下一個(gè)鄰接頂點(diǎn)序號(hào)
	virtual int getNextNeighbor (int v, int w){
	}
    //插入新頂點(diǎn), 點(diǎn)名為vertex
	virtual bool insertVertex (const T vertex){
	}
    //插入新邊(v1,v2), 權(quán)值cost
	virtual bool insertEdge (T v1, T v2, E cost){
	}
    //刪除名為 v 的頂點(diǎn)和所有與它相關(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é)點(diǎn)的類定義
public:
    int dest;		   //邊的鄰接(終)點(diǎn)序號(hào)
   	E cost;		   //邊上的權(quán)值
   	Edge_Vertices<T, E>* link;//下一個(gè)連接頂點(diǎn) 
	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;  } //重載!=運(yùn)算符,判邊不等
}; 



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

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

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

template<class T, class E>
void Graphlnk<T,E>::Connected_Component()//分別輸出連通分量 和輸出有向圖中連通分量的個(gè)數(shù) 
{	int Connected_Component_numbers=0;
	bool visited[this->numVertices];
	for(int i = 0 ; i <this->numVertices;i++)
		visited[i]=false;//初始化這個(gè)visited 數(shù)組
	for(int i =0; i < this->numVertices;i++)
	{
	if(!visited[i])//如果這個(gè)結(jié)點(diǎn)沒有被訪問過
	{
		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 的頂點(diǎn)出發(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];
      //對(duì)圖中所有頂點(diǎn)初始化訪問數(shù)組visited
     for (i = 0; i < this->numVertices; i++)
          visited[i] = false; //初始化為都未訪問過
    int loc = getVertexPos (v); //取名為 v 的頂點(diǎn)序號(hào)
    if(loc == -1) //名為 v 的頂點(diǎn)未找到
        cout<<"頂點(diǎn) "<<v<<"沒有找到，廣度優(yōu)先遍歷失敗。";
     else
     {
        cout << getValue (loc) << ' '; //訪問頂點(diǎn) v
        visited[loc] = true; //標(biāo)記頂點(diǎn) v 已訪問過
        //頂點(diǎn) v 進(jìn)隊(duì)列, 實(shí)現(xiàn)分層訪問
        queue<int> q; 
		 q.push(loc); //訪問過的頂點(diǎn)進(jìn)隊(duì)列 
        while (!q.empty() ) //循環(huán), 訪問所有結(jié)點(diǎn)
        {	loc = q.front();//記錄當(dāng)前隊(duì)列第一個(gè)頂點(diǎn)的值 
             q.pop(); // 然后記錄完讓它出隊(duì)列 
             w = getFirstNeighbor (loc); //取它的第一個(gè)鄰接頂點(diǎn) 
            while (w != -1)  //當(dāng)鄰接頂點(diǎn)w存在
            {   if (!visited[w]) //如果未訪問過
                 {   cout << getValue (w) << ' ';//訪問它然后輸出它 
                      visited[w] = true;	//標(biāo)記此頂點(diǎn)已經(jīng)訪問過
                      q.push(w); 	//頂點(diǎn)w進(jìn)隊(duì)列
                 }
                 w = getNextNeighbor (loc, w); //取下一個(gè)鄰接頂點(diǎn) 
            }
            
        } //外層循環(huán)，判隊(duì)列空否
    }
    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<<"頂點(diǎn)"<<v<<"不存在"<<"深度優(yōu)先遍歷失敗"<<endl;
	else //否則為存在
	DFS(sign,visited);
	delete[] visited; //深度優(yōu)先遍歷完成的話，就刪除這個(gè)數(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)//刪除邊這個(gè)比較簡(jiǎn)單 
{	
		if(v1<0||v2<0||v1>this->numVertices||v2>this->numVertices)//這種情況就是不符合，不符合就返回false  
		return false ;
		else //否則為符合的 
		{
		
	Edge_Vertices<T,E> *temp;//這是一個(gè)中間變量 
	temp=this->NodeTable[v1].next;//讓它先等于頂點(diǎn)表個(gè)的下一個(gè) 
	while(temp)
	{		
		if(temp->dest==v2)//如果一開始就是等于要?jiǎng)h除的那個(gè)頂點(diǎn)的話(可能會(huì)有誤解哦，這里不是刪除邊么，怎么刪除頂點(diǎn)？)
		//因?yàn)閯h除末頂點(diǎn)的話，就會(huì)少掉一條邊 
		{
			if(temp->link==NULL)//如果這條鏈只有這個(gè)待刪除的頂點(diǎn) 
			{
				this->NodeTable[v1].next=NULL;//讓頂點(diǎn)表的那個(gè)頂點(diǎn)的下一個(gè)頂點(diǎn)指向空 
				delete temp;	//刪除這個(gè)頂點(diǎn) 
				break;//跳出循環(huán) 
			}
			else{ //如果不為空的話 
		 	this->NodeTable[v1].next = temp->link;//讓頂點(diǎn)表的下一個(gè)頂點(diǎn)指向 待刪除 目標(biāo)頂點(diǎn)的下一個(gè) 
		 	delete temp;//刪除結(jié)點(diǎn) 
		 	break;
		 }
		}	if(temp)//防止內(nèi)存訪問出錯(cuò) 
		if(temp->link->dest ==v2)//不是第一個(gè)頂點(diǎn)是要?jiǎng)h除的頂點(diǎn)  這個(gè)if 語句記作 AAAAA  
		{	Edge_Vertices<T,E> *temp2;//定義一個(gè)中間變量temp2 
			temp2=temp->link;//讓temp  2指向 待刪除 目標(biāo)定點(diǎn) 
			temp->link=temp->link->link;//利用temp 斷開 目標(biāo)定點(diǎn) 與 子鏈的連接 
			delete temp2;//刪除目標(biāo)頂點(diǎn) 
			break;//跳出循環(huán) 
		}	if(temp)//防止內(nèi)存訪問出錯(cuò) 
	 		temp=temp->link;//根據(jù)這條語句，會(huì)回到剛才 AAAAA 那個(gè) 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) //刪除序號(hào)為 v 的頂點(diǎn)
{
    if(v<0||v>=this->numVertices)//如果下標(biāo)不符合規(guī)定 
	return false;
	else //否則為符合 
	{
	
	int del_vex_num=v;//記錄這個(gè)刪除的下標(biāo) 
	if(v!=this->numVertices-1)//如果不是刪除最后一個(gè)頂點(diǎn)的話 
	this->NodeTable[v]=this->NodeTable[--this->numVertices];//就用最后一個(gè)頂點(diǎn)頂?shù)哪菞l"鏈"替代這個(gè)待刪除頂點(diǎn)的"鏈" 
	//如果刪除的是最后一個(gè)頂點(diǎn)的話，自然就沒有影響了 
	else 
{
		this->numVertices--;
	int end_edg=0;//因?yàn)槿绻苯觿h掉這個(gè)點(diǎn)的話，那么這個(gè)點(diǎn)關(guān)聯(lián)的邊也要減掉
	Edge_Vertices<T,E> *p;
	p=this->NodeTable[v].next;
	while(p)
	{	
		if(p)
		{  end_edg++;//如果有一個(gè)頂點(diǎn)，且不為空的話，那么涉及的邊數(shù)就+1 
		 } 
		 p=p->link;
	 } 
	 this->numEdges-=end_edg;
}
	for(int i= 0 ; i < this->numVertices;i++)//此時(shí)的numVertices已經(jīng)-1 ，然后對(duì)這所有的鏈進(jìn)行操作，如果有將要?jiǎng)h除頂點(diǎn)與這個(gè)頂點(diǎn)相連，則刪除 
	{	Edge_Vertices<T,E> *temp;
		temp=this->NodeTable[i].next;
		//第一種情況：第一個(gè)連接的 頂點(diǎn)就是 將要?jiǎng)h除的那個(gè)頂點(diǎn)
		//這種情況很好做
		if(temp->dest ==v)
		{
			if(temp->link==NULL)//如果這條鏈只有一個(gè)結(jié)點(diǎn)，然后第一個(gè)結(jié)點(diǎn)恰好是這個(gè)將要?jiǎng)h除的頂點(diǎn)的話 
			{ 
				this->NodeTable[i].next=NULL;//這樣的話，直接刪掉它	
				this->numEdges--;
			}
			else //否則
			 {
			 this->NodeTable[i].next=temp->link;
			 delete temp;//刪除臨時(shí)的指針變量 
			 this->numEdges--;
			}
		 } 
		 else //第二種情況，就需要循環(huán)了，因?yàn)槊恳粋€(gè)頂點(diǎn)最多只有一個(gè) 將要?jiǎng)h除的那個(gè)頂點(diǎn)的下標(biāo) 
		 {//第一個(gè)結(jié)點(diǎn)的dest!=v 
		 	while(temp)
			 {
			 	if(temp->link)
				 {
				 
			 	if(temp->link->dest==v)//第一個(gè)的下一個(gè)頂點(diǎn)剛好是 這個(gè)dest 的話  
			 	{
			 		Edge_Vertices<T,E> *temp2;
			 		temp2=temp->link;//中間變量temp2; 
			 	  	temp->link=temp->link->link;//斷開這個(gè)將要?jiǎng)h除的頂點(diǎn)
					delete temp2;//刪除剛才的中間變量// 
					this->numEdges--;
					break;
				 } 
				}
				 temp=temp->link;//這個(gè)最終會(huì)變成NULL,最后跳出循環(huán); 
			  } 
		 }
	}
	if(v!=this->numVertices)//如果這個(gè)待刪除的下標(biāo)不等于 最后那個(gè)頂點(diǎn)的話 ，因?yàn)轫旤c(diǎn) 調(diào)動(dòng) 位置，所以需要改變 鏈中頂點(diǎn)下標(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)//就是說，最后的那個(gè)頂點(diǎn)要去前面 替換掉 剛才刪除的那個(gè)頂點(diǎn)的位置 ，因此，下標(biāo)也要改 
			{
				temp->dest=v;// 循環(huán)遍歷 出最后頂點(diǎn)的dest  然后用v  替換  
				break;
			}
			temp=temp->link;//移動(dòng) 
		}
	}
	}//第一個(gè)else 的右括號(hào) 
	return true;//刪除頂點(diǎn)成功 
}
template<class T , class E>
	E Graphlnk<T,E>::getWeight (int v1, int v2)//獲得兩個(gè)點(diǎn)之間的權(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這條鏈找一個(gè)點(diǎn)開始 
			while(temp)//然后循環(huán)，直到找到v2 
			{
			  if(temp->dest==v2)//找到了直接返回它的權(quán)值 
			  return temp->cost;
			  else 
			  temp=temp->link;	//沒找到，移動(dòng) 
			}
			return maxWeight;
			
		}
	}




template<class T , class E >
bool Graphlnk<T,E>::insertVertex (const T& vertex)//插入頂點(diǎn) ，插在之前定義的那個(gè)頂點(diǎn)表那里 
{
	if(this->numVertices<this->maxVertices)//如果圖當(dāng)前的頂點(diǎn)數(shù)小于 允許插入的最大頂點(diǎn)數(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); //這里還是直接是輸入定點(diǎn)名，用函數(shù)找這個(gè)頂點(diǎn)的下標(biāo) 
    int v2=getVertexPos(out);
	if(v1>-1 && v1<this->numVertices && v2>-1 && v2 < this->numVertices )//這兩個(gè)下標(biāo)都在頂點(diǎn)表里
	{     //將新邊的權(quán)值插入邊鄰接矩陣的第v1行,v2列,利用頭插法
	     Edge_Vertices<T,E> *temp =new Edge_Vertices<T,E>; //生成一個(gè)邊結(jié)點(diǎn)。
		 temp->dest=v2;// 記錄這個(gè)點(diǎn)的值 
		 temp->link=this->NodeTable[v1].next;//將它插在 v1 這個(gè)頂點(diǎn)的這條鏈里 ，這里采用頭插法 (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)建源點(diǎn)表數(shù)組
   NodeTable = new Vertex<T, E>[this->maxVertices];//分10個(gè)Vertex結(jié)點(diǎn)大小 的指針 數(shù)組 
    if (NodeTable == NULL) 
    {
	 cerr << "內(nèi)存分配出錯(cuò)！" << endl;  exit(1); 
	}
    for (int i = 0; i < this->maxVertices; i++)  
        NodeTable[i].next= NULL;//對(duì)NodeTable的指針進(jìn)行初始化 
}
//析構(gòu)函數(shù)：刪除一個(gè)鄰接表
template <class T, class E>
Graphlnk<T, E>::~Graphlnk()
 {	
   for (int vertex = 0; vertex < this->numVertices; vertex++ ){
        //current指向源點(diǎn)vertex邊鏈表的第1個(gè)鄰接點(diǎn)
	    Edge_Vertices<T, E> * current = NodeTable[vertex].next;
        while (current != NULL) {//鄰接點(diǎn)存在
            NodeTable[vertex].next = current->link; //脫鏈
            delete current; //釋放邊鏈表的第1個(gè)鄰接點(diǎn)
            // current重新指向邊鏈表的第1個(gè)鄰接點(diǎn)
            current = NodeTable[vertex].next;
        }
   	} 
   	delete []NodeTable; //刪除源點(diǎn)表數(shù)組
}
//返回序號(hào)為 v 的源點(diǎn)第1個(gè)鄰接點(diǎn)的序號(hào)(從0開始), 
//若未找到鄰接點(diǎn), 則返回-1
template <class T, class E>
int Graphlnk<T, E>::getFirstNeighbor (int v)
{   if (v != -1) //源點(diǎn)v存在
	 {  //current指向源點(diǎn)v的邊鏈表第1個(gè)鄰接點(diǎn)
         Edge_Vertices<T, E>* current = NodeTable[v].next;
	     if (current != NULL)//頂點(diǎn)v的第1個(gè)鄰接點(diǎn)存在
            //返回第1個(gè)鄰接點(diǎn)的序號(hào)
            return current ->dest;
   	}
   	return -1; //不存在第1個(gè)鄰接點(diǎn)，返回-1
}
//返回源點(diǎn)v和鄰接點(diǎn)w的下1個(gè)鄰接點(diǎn)的序號(hào)，
//若未找到下1個(gè)鄰接點(diǎn), 則返回-1
template <class T, class E>
int Graphlnk<T, E>::getNextNeighbor (int v, int w)
{  if (v != -1) { //源頂點(diǎn) v 存在
        Edge_Vertices<T, E>* current = NodeTable[v].next;//終頂點(diǎn)current 
        while (current != NULL && current->dest != w)
             current = current->link; //先找到終頂點(diǎn) w
	    if (current != NULL && current->link != NULL) 
	        //返回w的下1個(gè)鄰接頂點(diǎn)序號(hào)
            return current->link->dest;
   	}
   	return -1; //未找到下1個(gè)鄰接頂點(diǎn)，返回-1
}
template <class T, class E>
void Graphlnk<T,E>::Enter()
{	int Count,vertexs,Edges;
	T e1,e2;
	cout<<"圖中共有多少個(gè)頂點(diǎn)？";
	cin>>vertexs;
	cout<<"輸入圖中共 "<<vertexs<<" 個(gè)頂點(diǎn)名：";
    //輸入圖中全部頂點(diǎn)名
	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個(gè)頂點(diǎn)名和權(quán)值：";
		cin>>e1>>e2>>weight;
		if(insertEdge(e1,e2,weight)) 
		      Count++;
		else
                cout<<"頂點(diǎn)名有誤，重新輸入這條邊！"<<endl;
	}
}
// 輸出圖中所有頂點(diǎn)和邊的信息
template <class T, class E>
void Graphlnk<T, E>::Print(void)
{	int row,column;
	E weight;
	cout<<"圖中共有 "<<this->numVertices<<" 個(gè)頂點(diǎn)和 "<<this->numEdges<<" 條邊："<<endl;

	
for(row=0;row<this->numVertices;row++)
	{
		//按行號(hào)取出序號(hào)為row的頂點(diǎn)名并輸出
		cout<<"序號(hào)"<<row<<"源點(diǎn)"<<"["<<getValue(row)<<"]"<<"->";
		Edge_Vertices<T, E> *temp;
		temp=this->NodeTable[row].next;
		if(temp)//可能它的下一個(gè)頂點(diǎn)直接就是空 
		{
		
		while(temp->link)
		{
			cout<<"["<<"鄰接點(diǎn)"<<temp->dest<<"]";
			if(this->withCost)
			cout<<"["<<"權(quán)值"<<temp->cost<<"]";
			cout<<"[-]->" ;
		temp=temp->link;
		
		}
		cout<<"["<<"鄰接點(diǎn)"<<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<<"請(qǐng)輸入你想要?jiǎng)h除的一個(gè)頂點(diǎn)"<<endl;
//	cin>>del;
// 	int index= graph.getVertexPos(del);
//	if(graph.removeVertex (index))
//	cout<<"刪除成功"<<endl;
//	else 
//	cout<<"刪除失敗";
//	graph.Print();
//	cout<<"請(qǐng)輸入你想要?jiǎng)h除那條邊的兩個(gè)頂點(diǎn)"<<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<<"請(qǐng)輸入一個(gè)頂點(diǎn)來進(jìn)行深度優(yōu)先遍歷"<<endl;
// string dfs;
// cin>>dfs;
// graph.DFS(dfs);
// cout<<endl; 
//cout<<"請(qǐng)輸入一個(gè)頂點(diǎn)來進(jìn)行廣度優(yōu)先遍歷"<<endl;
//string bfs;
//cin>>bfs;
//graph.BFS(bfs);
//cout<<endl;
//graph.Connected_Component();
	string  a,b;
	cout<<"輸入求最短路徑的始頂點(diǎn)：";cin>>a;
	int v = graph.getVertexPos(a);
	cout<<"輸入求最短路徑的終頂點(diǎn)：";cin>>b;
	int w = graph.getVertexPos(b);
	graph.Dijkstra(v);
	graph.Print(v,w);
//system("PAUSE");
}