C++ 最短路径 C++ Dijkstra算法之求图中任意两顶点的最短路径

#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;	//最大顶点数不妨设为30 
template <class T, class E>
class Graph {
protected:
    int maxVertices=10;//图中最大顶点数
    int numVertices=0;//图中当前顶点数
    int numEdges=0;//图中当前边数
    bool direction=false;//图中边的是否有方向
    bool withCost=false;//图中的边是否带权
    //返回顶点名vertex的序号(从0开始)
	int getVertexPos (T vertex);	
public:   
	void DFS (const T& v)
	{
		
	} 
	
	void BFS (const T& v)
	{
	} 
                                     
    Graph(int sz , bool direct, bool cost); //构造函数
    ~Graph()//析构函数 
	{}	
			//析构函数
    bool GraphEmpty () const	//判图是否为空，因为不需要修改，因此设置为常成员函数 
    {
	  return numEdges == 0;  
	}
    bool GraphFull() const;         //判图是否为满
    //返回图中当前顶点数
   	int NumberOfVertices () 
	{ 
	   return numVertices;
	}
    //返回图中当前边数
	int NumberOfEdges ()
	{ 
	 return numEdges;
	}
	//取回序号为 i 的顶点值(顶点名)
	virtual T getValue (int i){
	}
    //取顶点序号为v1,v2的边上权值
    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), 权值cost
	virtual bool insertEdge (T v1, T v2, E cost){
	}
    //删除名为 v 的顶点和所有与它相关联的边
	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 {		   //边结点的类定义
public:
    int dest;		   //边的邻接(终)点序号
   	E cost;		   //边上的权值
   	Edge_Vertices<T, E>* link;//下一个连接顶点 
	Edge_Vertices (int num=0, Edge_Vertices<T, E>* next=NULL, E weight=NULL) //构造函数
    : 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;		      //源顶点的名字(数据)
	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) 	//找到目标顶点所在的序号 期中 vertx 参数为string 类型 
	{   for (int i = 0; i < this->numVertices; i++)
	        if (NodeTable[i].data == vertx) return i;
 	     return -1; 
	}             //构造函数
    Graphlnk( int sz=DefaultVertices, bool direct=false, bool cost=false ); 
   	~Graphlnk(); //析构函数
    T getValue (int i) { //取序号为 i 的顶点名
	    return (i >= 0 && i < this->numVertices) ? 
             NodeTable[i].data : NULL;
    }
	E getWeight (int v1, int v2);	//取边(v1,v2)权值 
	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; 为类数据成员
template<typename T, typename E>
void Graphlnk<T,E>::Print(int v, int w)//输出从V 到W 的最短路径 
 {  //因为v和w都是 int 型,即输入类型的下标，因此，要用getValue 获得原来的输入的顶点名字 
	cout<<"始顶点 "<<this->getValue(v)<<" 到终顶点 "<<this->getValue(w)<<" 的最短路径为:"<<endl;
	int current=w, previous;
	stack<char > Road;//定义一个char类型的栈，因为是用顶点回溯 (即从 最后的一个顶点 往前找前驱顶点的，因此我们可以用栈(后进先出的特性))
	//用栈后进先出的特性可以 在出栈的时候 按顺序输出从 开始顶点到目的顶点的  路径 ，如果对输出没有要求的话就不需要栈，可以直接输出
	//不过输出的结果会倒置(从目的顶点 一步一步往回走 ，直到找到开始顶点) 
	stack<int >Road_Weight;//如果 顶点 要按顺序输出，还想输出 这两个顶点间的权值的话，那么这些权值也是倒置的，因此权值也需要利用栈的特性输出 
	Road.push(this->getValue(w)[0]);//因为this->getValue(w) 返回的是一个string 类型， 本次测试的顶点都是要么是单个数字名字，或者单个字母名字
	// 因为是char 类型，因此只能单个字母进去，所以this->getValue(w)[0] 就是取第一个 字母/数字 
	while( current!=v )//如果这个顶点不等于 开始顶点的话 
	{
		previous=path[current];//找它的上一个顶点 
		Road.push(this->getValue(path[current])[0]);//名字入栈 
		Road_Weight.push(this->getWeight(previous,current));//权值入栈 
		current=previous; 
	}
	string  p;//string 变量 p 用来记录前面的顶点和 做临时变量 
	string  e;//string 变量 e 用来输出顶点名字 
	int q;
	int x=1;//一个标志 
	int i = 1;//第i步 
	while(Road.empty()!=true)
	{  
	//这个if 语句只运行一次，为什么呢，考虑到 奇数个顶点的话，那么，最短路径至少有两个顶点，如果第一次就把顶点输出完了
	//那么后面的if语句都不会运行了，但是如果 是奇数个顶点呢？ 奇数个顶点的话，程序编译不会出错，但是运行会中断， 即栈已经空了，不能弹栈了
	//因此，执行一次这个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在后面不再 用来接收 栈弹出的顶点，而是充当一个临时变量-------用上一个顶点 的末顶点 进行覆盖 
	   e=Road.top();//取栈首顶点 
	   Road.pop();// 弹栈 
	    q=Road_Weight.top();//取栈里的首权值 
	   Road_Weight.pop();
	   cout<<"第"<<i++<<"步为:  "<<"顶点"<<p<<"-->到顶点"<<e<<"  长度为: "<<q<<endl;	
	   }
	   
	}
	cout<<"最短路径总长度为："<<dist[w]<<endl;//输出最短路径长度 
}

template<class T,class E>
//Graphlnk是一个带权有向图.数据成员E dist[v][j],
//0≤j<n, 是当前求到的从顶点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，标记顶点是否已经在最短路径的顶点集里 
	this->path=new int [this->numVertices];//路径数组(跳跃式，要用回溯才能找出整个完整的路径) 
	this->dist= new int [this->numVertices];//源点v到任意顶点vi的最短路径数组， 
	for(int i = 0 ; i < this->numVertices;i++)//初始化 
	{	
		s[i]=false;//把所有的顶点都标记为:未在最短路径顶点集 
		if(this->getWeight(v,i)!=maxWeight)//如果有v和vi间如果有权值的话，那么，就是说，这两点是连通的。 
		// 既然两点是连通的，那么，这个路径就有可能是最短的。 
		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这个顶点的前驱 是v (如果v==i 就让自己指向自己) 
		else 
		path[i]=-1;// 否则vi和 v 没有路，即两点间不连通  
	}
	dist[v]=0;//首先，规定，v->v 即自己到自己的距离是0 
	s[v]=true;//将开始顶点v放入并查集数组中 
	int min;//最小路径的一个值 
	for(int i = 1; i <this->numVertices;i++)
	{
		 min = maxWeight;//首先要让这个最小值足够大，然后后面的那些路径权值才会比这个值小然后把它替换为真正的"最小值" 
		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出发，不断的去找和它相连接的顶点vi(i取任意正整数，即顶点可能不知有一个，可能是多个)
		//然后看v到vi的路径短一点还是,v到Vnew再到Vi,如果是v到Vnew 再到vi 比 直接从v到vi更短的话，那么就替换 v到Vw的最小距离dist[w]
		//并且规定w的前驱顶点为k ,即:path[w]=k; (此时w还没有在最短路径顶点集合里面) 
		//由此我们可以知道：既然每加入一个 顶点到 最短路径顶点集里面，都会执行这段代码。 
		//然后 都会从刚加入的那个顶点去 找遍所有 和它关联的顶点，所以，如果说这个加入的顶点如果 和目的顶点X相连，那么加入这个顶点后
		// 执行下面的代码，就可以求出当前从始顶点到目的顶点X的最短路径,为什么是当前？因为这个最小是当前最小的，因为还有其他顶点未加入顶点集
		//即有可能从 v出发 经过某个 未加入  最短路径顶点集合里的顶点 再到X 的路径大小 比 从v到原先那个加入  最短路径顶点集合里的顶点 再到x 的路径要小
		//所以，下面的代码每次执行都会求得 一个临时的最短路径，如果顶点都加入完了，那么，自然是最短路径了  
		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顶点的前驱是k 
		}
		
	}
	delete []s ;//删除标记数组
	//输出代码可以在函数体里，也可以 加一个print函数 在函数体外 
//	cout<<"始顶点 "<<v<<" 到终顶点 "<<w<<" 的最短路径为：终顶点 "<< w;
//	int current=w, previous;
//	while( current!=v )
//	{
//		previous=path[current];
//		cout<<"路径"<<path[current];
//		cout<<"最小距离"<<dist[current];
//		cout<<" <-权值[ "<<getWeight(previous,current)<<" ]-顶点 "<<previous;
//		current=previous;
//	}
//	cout<<"。最短路径总长度为："<<dist[w]<<endl;
}

template<class T, class E>
void Graphlnk<T,E>::Connected_Component()//分别输出连通分量 和输出有向图中连通分量的个数 
{	int Connected_Component_numbers=0;
	bool visited[this->numVertices];
	for(int i = 0 ; i <this->numVertices;i++)
		visited[i]=false;//初始化这个visited 数组
	for(int i =0; i < this->numVertices;i++)
	{
	if(!visited[i])//如果这个结点没有被访问过
	{
		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;//结束后删除数组	
}
//从名为 v 的顶点出发广度优先遍历
template <class T, class E> 
void Graphlnk<T,E>::BFS(const T& v)
{    int i, w; 
      //创建访问标记数组
     bool* visited = new bool[this->numVertices];
      //对图中所有顶点初始化访问数组visited
     for (i = 0; i < this->numVertices; i++)
          visited[i] = false; //初始化为都未访问过
    int loc = getVertexPos (v); //取名为 v 的顶点序号
    if(loc == -1) //名为 v 的顶点未找到
        cout<<"顶点 "<<v<<"没有找到，广度优先遍历失败。";
     else
     {
        cout << getValue (loc) << ' '; //访问顶点 v
        visited[loc] = true; //标记顶点 v 已访问过
        //顶点 v 进队列, 实现分层访问
        queue<int> q; 
		 q.push(loc); //访问过的顶点进队列 
        while (!q.empty() ) //循环, 访问所有结点
        {	loc = q.front();//记录当前队列第一个顶点的值 
             q.pop(); // 然后记录完让它出队列 
             w = getFirstNeighbor (loc); //取它的第一个邻接顶点 
            while (w != -1)  //当邻接顶点w存在
            {   if (!visited[w]) //如果未访问过
                 {   cout << getValue (w) << ' ';//访问它然后输出它 
                      visited[w] = true;	//标记此顶点已经访问过
                      q.push(w); 	//顶点w进队列
                 }
                 w = getNextNeighbor (loc, w); //取下一个邻接顶点 
            }
            
        } //外层循环，判队列空否
    }
    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<<"不存在"<<"深度优先遍历失败"<<endl;
	else //否则为存在
	DFS(sign,visited);
	delete[] visited; //深度优先遍历完成的话，就删除这个数组 
}
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);//否则回退 然后继续搜索 
	}
}


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;//跳出循环 
			}
			else{ //如果不为空的话 
		 	this->NodeTable[v1].next = temp->link;//让顶点表的下一个顶点指向 待删除 目标顶点的下一个 
		 	delete temp;//删除结点 
		 	break;
		 }
		}	if(temp)//防止内存访问出错 
		if(temp->link->dest ==v2)//不是第一个顶点是要删除的顶点  这个if 语句记作 AAAAA  
		{	Edge_Vertices<T,E> *temp2;//定义一个中间变量temp2 
			temp2=temp->link;//让temp  2指向 待删除 目标定点 
			temp->link=temp->link->link;//利用temp 断开 目标定点 与 子链的连接 
			delete temp2;//删除目标顶点 
			break;//跳出循环 
		}	if(temp)//防止内存访问出错 
	 		temp=temp->link;//根据这条语句，会回到刚才 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--;//记得删完 边数要 -1; 
return true;//删除成功返回true  
}


template<class T , class E >
bool Graphlnk<T,E>::removeVertex (int v) //删除序号为 v 的顶点
{
    if(v<0||v>=this->numVertices)//如果下标不符合规定 
	return false;
	else //否则为符合 
	{
	
	int del_vex_num=v;//记录这个删除的下标 
	if(v!=this->numVertices-1)//如果不是删除最后一个顶点的话 
	this->NodeTable[v]=this->NodeTable[--this->numVertices];//就用最后一个顶点顶的那条"链"替代这个待删除顶点的"链" 
	//如果删除的是最后一个顶点的话，自然就没有影响了 
	else 
{
		this->numVertices--;
	int end_edg=0;//因为如果直接删掉这个点的话，那么这个点关联的边也要减掉
	Edge_Vertices<T,E> *p;
	p=this->NodeTable[v].next;
	while(p)
	{	
		if(p)
		{  end_edg++;//如果有一个顶点，且不为空的话，那么涉及的边数就+1 
		 } 
		 p=p->link;
	 } 
	 this->numEdges-=end_edg;
}
	for(int i= 0 ; i < this->numVertices;i++)//此时的numVertices已经-1 ，然后对这所有的链进行操作，如果有将要删除顶点与这个顶点相连，则删除 
	{	Edge_Vertices<T,E> *temp;
		temp=this->NodeTable[i].next;
		//第一种情况：第一个连接的 顶点就是 将要删除的那个顶点
		//这种情况很好做
		if(temp->dest ==v)
		{
			if(temp->link==NULL)//如果这条链只有一个结点，然后第一个结点恰好是这个将要删除的顶点的话 
			{ 
				this->NodeTable[i].next=NULL;//这样的话，直接删掉它	
				this->numEdges--;
			}
			else //否则
			 {
			 this->NodeTable[i].next=temp->link;
			 delete temp;//删除临时的指针变量 
			 this->numEdges--;
			}
		 } 
		 else //第二种情况，就需要循环了，因为每一个顶点最多只有一个 将要删除的那个顶点的下标 
		 {//第一个结点的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,最后跳出循环; 
			  } 
		 }
	}
	if(v!=this->numVertices)//如果这个待删除的下标不等于 最后那个顶点的话 ，因为顶点 调动 位置，所以需要改变 链中顶点下标名字 
	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)//就是说，最后的那个顶点要去前面 替换掉 刚才删除的那个顶点的位置 ，因此，下标也要改 
			{
				temp->dest=v;// 循环遍历 出最后顶点的dest  然后用v  替换  
				break;
			}
			temp=temp->link;//移动 
		}
	}
	}//第一个else 的右括号 
	return true;//删除顶点成功 
}
template<class T , class E>
	E Graphlnk<T,E>::getWeight (int v1, int v2)//获得两个点之间的权值 
	{
		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)//然后循环，直到找到v2 
			{
			  if(temp->dest==v2)//找到了直接返回它的权值 
			  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)//如果图当前的顶点数小于 允许插入的最大顶点数，则可以插入 
	{
		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); //这里还是直接是输入定点名，用函数找这个顶点的下标 
    int v2=getVertexPos(out);
	if(v1>-1 && v1<this->numVertices && v2>-1 && v2 < this->numVertices )//这两个下标都在顶点表里
	{     //将新边的权值插入边邻接矩阵的第v1行,v2列,利用头插法
	     Edge_Vertices<T,E> *temp =new Edge_Vertices<T,E>; //生成一个边结点。
		 temp->dest=v2;// 记录这个点的值 
		 temp->link=this->NodeTable[v1].next;//将它插在 v1 这个顶点的这条链里 ，这里采用头插法 (temp 街上NodeTable[v1]的后面 一大串(当然一开始为空))
		 //比如这一大串为ABCDE  然后temp  接上去就为 temp->ABCDE; 
		 if(this->withCost==true)//如果需要记录权值 
		 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 语句)
}
//构造函数建立邻接表
template <class T, class E>
Graphlnk<T, E>::Graphlnk (int sz,bool direct, bool cost):Graph<T,E>(sz, direct, cost)
{	//创建源点表数组
   NodeTable = new Vertex<T, E>[this->maxVertices];//分10个Vertex结点大小 的指针 数组 
    if (NodeTable == NULL) 
    {
	 cerr << "内存分配出错！" << endl;  exit(1); 
	}
    for (int i = 0; i < this->maxVertices; i++)  
        NodeTable[i].next= NULL;//对NodeTable的指针进行初始化 
}
//析构函数：删除一个邻接表
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; //删除源点表数组
}
//返回序号为 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<<"图中的边带权吗(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个顶点名和权值：";
		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<<"["<<"权值"<<temp->cost<<"]";
			cout<<"[-]->" ;
		temp=temp->link;
		
		}
		cout<<"["<<"邻接点"<<temp->dest<<"]";
		if(this->withCost)
			cout<<"["<<"权值"<<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<<"请输入一个顶点来进行深度优先遍历"<<endl;
// string dfs;
// cin>>dfs;
// graph.DFS(dfs);
// cout<<endl; 
//cout<<"请输入一个顶点来进行广度优先遍历"<<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");
}