/*----------------------图的邻接表示存储------------------------*/
//无向图

#define MAX_VEXNUM 20  //最大顶点数

struct ArcNode{
	int adjvex;      //该弧所指向的顶点的位置
	ArcNode *nextarc; //指向下一条弧的指针
};

template <class DT>
struct VNode{
	DT data;    //顶点信息
	ArcNode *firstarc;//指向第一条依附该顶点的指针
};

template <class DT>
struct ALGraph{
	VNode<DT> vertices[MAX_VEXNUM];//顶点集
	int vexnum;//顶点数
	int arcnum;//边数
};

template <class DT>
void  DispG(ALGraph<DT> G)
{
	int i;
	ArcNode *p;
	cout<<G.vexnum<<"个顶点:"<<endl;//输出顶点
	for(i=0;i<G.vexnum;i++)
	{
		cout<<G.vertices[i].data<<" ";
	}
	cout<<endl;
	cout<<G.arcnum<<"条弧（边）:"<<endl;
	for(i = 0;i<G.vexnum;i++)
	{
		p = G.vertices[i].firstarc;
		while(p)
		{
			if(i<p->adjvex)					//避免了无向的时候一条边被输出两次
			{
				cout<<"("<<G.vertices[i].data<<","
					<<G.vertices[p->adjvex].data<<")"<<'\t';
			}
			p = p->nextarc;
		}
	}
	cout<<endl;
}


template <class DT>
int LocateVex(ALGraph<DT> G, DT v)
{
	for(int i=0;i<G.vexnum;i++)
	{
		if(G.vertices[i].data == v)
		{
			return i;
		}
	}
	return -1;
}

template <class DT>
void  CreateUDG(ALGraph<DT> &G)
{
	int i,j,k;
	DT v1,v2;
	ArcNode *p;
	cout<<"请输入无向图的顶点数 ";						// 1. 输入顶点数、边数
	cin>>G.vexnum ;
	cout<<"请输入无向图的边数 ";								
	cin>>G.arcnum ;
	cout<<"请输入"<<G.vexnum<<"个顶点的值"<<endl;		// 2. 输入顶点值
	for(i = 0;i<G.vexnum;i++)					// 初始化顶点结点
	{
		cin>>G.vertices[i].data;
		G.vertices[i].firstarc = NULL;
	}
	//cout<<"请输入每条边两个邻接点： "<<endl;
	for(k=0;k<G.arcnum;k++)	//构造表结点链表
	{
		cout<<"请输入边的两个顶点值: "<<endl;
		cin>>v1>>v2;
		i = LocateVex(G,v1);
		j = LocateVex(G,v2);
		if(i<0 || j<0 || i==j)
		{
			cout<<"顶点信息错，重新输入！"<<endl;
			k--;
			continue;
		}
        p = new ArcNode; //创建一个新的弧结点
		p->adjvex = j; 
		p->nextarc = G.vertices[i].firstarc; //插在表头
		G.vertices[i].firstarc = p;
		p = new ArcNode; //创建一个新的弧结点
		p->adjvex = i;
		p->nextarc = G.vertices[j].firstarc; //插在表头
		G.vertices[j].firstarc = p;
	}
}


template <class DT>
void  DestroyGraph(ALGraph<DT> G)
{
	int i;
	ArcNode *p,*q;
	for(i = 0;i<G.vexnum;i++)//从顶点序号为0的顶点开始依次释放掉相应的邻接表
	{
		p = G.vertices[i].firstarc;
		while(p)
		{
			q = p->nextarc;
			delete p;//删除弧结点
			p = q;
		}
	}
	G.arcnum = 0;
	G.vexnum = 0;
}

template <class DT>
bool GetVex(ALGraph<DT> G, int k,DT &v)
{
	if(k<0||k>=G.vexnum)					//顶点不存在
		return false;
	v=G.vertices[k].data;
		return true;
}

template <class DT>
bool PutVex(ALGraph<DT> &G, DT &u,DT v)
{
	int k = LocateVex(G,u);
	if(k<0)							//该顶点不存在
		return false;
	G.vertices[k].data = v;
	return true;
}

template <class DT>
int  FirstAdjVex(ALGraph<DT> G, int u)
{
	ArcNode * p;
	if(u<0 || u>=G.vexnum)								// 顶点不存在 
		return -1;	
	p = G.vertices[u].firstarc;//p指向下标为i的第一个邻接点
	if(p)
	{
		return p->adjvex;
	}
	else
	{
		return -1;
	}
}

template <class DT>
int  NextAdjVex(ALGraph<DT> G, int u,int w)
{
	ArcNode *p;
	if(u<0 || u>=G.vexnum || w<0 
		   || w>=G.vexnum )				// 参数不合理							
		return -1;	
	p = G.vertices[u].firstarc;
	while(p &&(p->adjvex!=w))
		//让p指向顶点w
	{
		p = p->nextarc;
	}
	if(!p||!p->nextarc) //没找到w或w是最后一个顶点
		return -1;
	else
		//找到w且w不是最后一个顶点
	{
		return p->nextarc->adjvex;
	}
}

template <class DT>
bool  InsertVex(ALGraph<DT> &G, DT v)
{
	int j;
	char ans;
	DT  w;
	if(G.vexnum > MAX_VEXNUM)
	{
		cout<<"无存储空间，不能插入!"<<endl;
		return false;
	}
	G.vertices[G.vexnum].data = v;
	G.vertices[G.vexnum].firstarc = NULL;
	G.vexnum++;
	cout<<"创建边吗（Y/N)?"<<endl;
	cin>>ans;
	while(ans=='Y'|| ans=='y')
	{
		cout<<"输入另一个顶点值:"<<endl;
		cin>>w;
		j=LocateVex(G,w);
		if(j>=0)										// 顶点存在
			InsertArc(G,v,w);
		else
			cout<<w<<"\n顶点不存在！";
		cout<<"继续创建边吗（Y/N)?"<<endl;
		cin>>ans;
	};
	return true;	 
}


template <class DT>
bool  InsertArc(ALGraph<DT> &G, DT v,DT w)
{
	ArcNode *p;
	int i,j;
	i = LocateVex(G,v);
	j = LocateVex(G,w);
	if(i<0||j<0 || i==j)				// 顶点不存在或两端点相同,不能插入
	{
		cout<<"\n顶点不存在或两顶点相同，不能插入！"<<endl;
		return false;
	}
	p=G.vertices[i].firstarc;
	while(p)
	{
		if(p->adjvex==j)
		{
			cout<<"边存在，不能插入！"<<endl;
			return false;
		}
		p=p->nextarc;
	}
	G.arcnum++;
	p = new ArcNode;
	p->adjvex = j; 
	p->nextarc = G.vertices[i].firstarc;		//(v,w)边结点插在第i条链表表头
	G.vertices[i].firstarc = p;
	p = new ArcNode;
	p->adjvex = i;								//(w,v)边结点插在第j链表表头
	p->nextarc = G.vertices[j].firstarc;
	G.vertices[j].firstarc = p;
	return true;
}

template <class DT>
bool  DeleteArc(ALGraph<DT> &G, DT v,DT w)
{
	ArcNode *p,*q;
	int i,j;
	cout<<"Hello DeleteArc!"<<endl;
	cout<<"删除边顶点为："<<endl;
	cout<<"("<<v<<","<<w<<")"<<endl;
	i = LocateVex(G,v);
	j = LocateVex(G,w);
    cout<<"删除边顶点序号为："<<endl;
	cout<<"("<<i<<","<<j<<")"<<endl;
	if(i<0||j<0||i == j)
	{
		cout<<"\n边不存在！"<<endl;						 
		return false;
	}
	p = G.vertices[i].firstarc;
	while(p && p->adjvex!=j)						// p不空且p指向的不是待删弧结点
	{
		q = p;
		p = p->nextarc;
	}
	if(p&&p->adjvex ==j)							// 找到边<v,w>
	{
		if(p == G.vertices[i].firstarc)				// 第1个边结点
		{
			G.vertices[i].firstarc = p->nextarc;
		}
		else										// 非第1个边结点
		{
			q->nextarc = p->nextarc;
		}
		delete p;
		G.arcnum--;
		p = G.vertices[j].firstarc;
		while(p&&p->adjvex!=i)						// p不空且q指向的不是待删弧结点
		{
			q = p;
			p = p->nextarc;
		}
		if(p == G.vertices[j].firstarc)				// 第1个边结点
		{
			G.vertices[j].firstarc = p->nextarc;
		}
		else										// 非第1个边结点
		{
			q->nextarc = p->nextarc;
		}
		delete p;
	}
	cout<<"Bye-bye DeleteArc!"<<endl;
	return true;
}

template <class DT>
bool  DeleteVex(ALGraph<DT> &G, DT v)
{
	int i,j; 
	ArcNode *p;
	DT w;
	i = LocateVex(G,v);
	cout<<"将删除第"<<i<<"个顶点！"<<endl;
	if(i<0)
	{
		cout<<"顶点不存在！"<<endl;						// 顶点不存在
		return false;
	}
	p = G.vertices[i].firstarc;
	while(p)											// 删除以v为邻接点边
	{
		j=p->adjvex;
		cout<<"删除边顶点序号为："<<endl;
		cout<<"("<<i<<","<<j<<")"<<endl;
		GetVex(G,j,w);
		cout<<"删除边顶点为："<<endl;
		cout<<"("<<v<<","<<w<<")"<<endl;
		DeleteArc(G,v,w);
		p=G.vertices[i].firstarc;
	}
	for(j=i+1;j<G.vexnum;j++)							// 顶点v后面的顶点前移
	{
		G.vertices[j-1].data = G.vertices[j].data;
		G.vertices[j-1].firstarc=G.vertices[j].firstarc;
	}
	G.vexnum--;
	return true;
}

// 算法6.8
template <class DT>
void  DFS(ALGraph<DT> G, int v)
{
	int w;
	visited[v] = true;									// 已访问
	cout<<G.vertices[v].data;							// 访问顶点
	for(w = FirstAdjVex(G,v);w>=0;w=NextAdjVex(G,v,w))
	{
		if(!visited[w])
			DFS(G,w);
	}
}

// 算法6.9
template <class DT>
void DFSTraverse(ALGraph<DT> G)
{
	int i ;
   	for(i = 0;i<G.vexnum;i++)
		visited[i] = false;
    for(i = 0;i<G.vexnum;i++)		//对每个未被访问的顶点进行深度优先遍历
    {
	   if(!visited[i])
		   DFS(G,i);
    }
	//cout<<endl;
    return;
}

// 算法6.13
template <class DT>
void BFS(ALGraph<DT> G, int v)
{
	int w;
	ArcNode *p;
	LinkQueue<int> Q;
	InitQueue(Q);
	cout<<G.vertices[v].data;
	visited[v]=true;
	EnQueue(Q,v);
	while(!QueueEmpty(Q))
	{
		DeQueue(Q,v);
		p=G.vertices[v].firstarc;
		while(p)
		{
			w=p->adjvex;
			if(!visited[w])
			{
				cout<<G.vertices[w].data;
				visited[w]=true;
				EnQueue(Q,w);
			}
			p=p->nextarc;
		}
	}
}


template <class DT>
bool  BFSTraverse(ALGraph<DT> G)
{
	int i; 
	for(i = 0;i<G.vexnum;i++)
		visited[i] = false;
	for(i = 0;i<G.vexnum;i++)
		if(!visited[i])
			BFS(G,i);
	//cout<<endl;
	return true;
}