/*--------------------------无向图网邻接矩阵表示-----------------------------*/

#define MAX_VEXNUM 20								// 最大顶点数
#define INF 1000									// 无穷大
 
template <class DT>
struct MGraph										// 图的邻接矩阵表示存储定义
{
	DT vexs[MAX_VEXNUM];							// 顶点信息，设权值为整型
	int arcs[MAX_VEXNUM][MAX_VEXNUM];
	int vexnum,arcnum;								// 顶点数和边数
};


template <class DT>
void DispG(MGraph<DT> G)							// 显示图信息
{
	int i,j; 
	DT u,v;
	cout<<G.vexnum<<"个顶点："<<endl;
	for(i=0;i<G.vexnum;i++)
		cout<<G.vexs[i]<<"  ";
	cout<<endl;
	cout<<G.arcnum<<"条边信息如下："<<endl;
	for(i=0;i<G.vexnum;i++)
	{
		for(j=i+1;j<G.vexnum;j++)
			if (G.arcs[i][j]!=INF)
			{
				GetVex(G,i,u);
				GetVex(G,j,v);
				cout<<'('<<u<<","<<v<<","<<G.arcs[i][j]<<")"<<'\t';
			}
	}
	cout<<endl;
}


//算法6.1											顶点定位
template <class DT>
int LocateVex(MGraph<DT> G,DT v)
{
	for(int i = 0;i<G.vexnum;i++)
	{
		if(G.vexs[i] == v)
		{
			return i;
		}
	}
	return -1;
}

//6.2 创建无向图
template <class DT>
void CreateUDN(MGraph<DT> &G)
{
	int i,j,k,weight;	 
	DT v1,v2;
	cout<<"请输入无向网的顶点数 ";						// 1. 输入顶点数、边数
	cin>>G.vexnum ;
	cout<<"请输入无向网的边数 ";								
	cin>>G.arcnum ;
	cout<<"请输入"<<G.vexnum<<"个顶点的值（单个字符）"<<endl;		// 2. 输入顶点值
	for(i = 0;i<G.vexnum;i++)
		cin>>G.vexs[i];
	for(i=0;i<G.vexnum;i++)								// 3.邻接矩阵初始化
		for(j=0;j<G.vexnum;j++)
			G.arcs[i][j]=INF;
	cout<<"请输入各条边的两个邻接点"<<endl;				// 4.创建各条边
	for( k=0;k<G.arcnum;k++)
	{
		cout<<"输入第"<<k<<"条边的两个顶点和权值："<<endl;
		cin>>v1>>v2;									// 4.1 输入边的两个邻接点和边权值
		cin>>weight;									
		i = LocateVex(G,v1);							// 4.2 定位两个邻接点
		j = LocateVex(G,v2);
		if(i<0 || j<0 || i==j)
		{
			cout<<"顶点信息错，重新输入！"<<endl;
			k--;
			continue;
		}
		G.arcs[i][j]=weight;									// 4.3 修改邻接矩阵
		G.arcs[j][i]=weight;		 
	}
}


template <class DT>
bool GetVex(MGraph<DT> G, int k, DT &v)					// 获取第 u 个顶点值v
{				
	if(k<0 || k>=G.vexnum)								// u不存在，返回false
		return false;
	else
	{
		v=G.vexs[k];
	    return true;
	}
}


template <class DT>
bool PutVex(MGraph<DT> &G,DT &u,DT v)					// 为第u个顶点赋值
{
	int k;
	k=LocateVex(G,u);
	if(k<0 )											// u不存在，返回false
		return false;	
	else												// u存在，赋值
	{
		G.vexs[k] = v;
		return true;
	}
}

//算法6.3												按值查找第一邻接点
template <class DT>
int FirstAdjvex(MGraph<DT> G,int u)
{
	if(u<0 || u>=G.vexnum)								// 顶点不存在 
		return -1;										// 无邻接点，返回-1
	for(int j=0;j<G.vexnum;j++)							// 扫描邻接矩阵第u行
		if(G.arcs[u][j]!=INF)								// 如果有非零元，
			return j;									// 第一个非零元所在列号，为其邻接点序号
	return -1;											// 否则，无邻接点，返回-1					
}

template <class DT> 
int NextAdjvex(MGraph<DT> G,int u,int w)				// 查找第u个顶点邻接点W的下一个邻接点
{
	if(u<0 || u>=G.vexnum || w<0 
		|| w>=G.vexnum || G.arcs[u][w]==INF )			// 参数不合理							
		return -1;										//  无邻接点
	for(int j=w+1;j<G.vexnum;j++)						// 扫描邻接矩阵第u行w列后的元素
		if(G.arcs[u][j]!=INF)							// 如果有非无穷元
			return j;									// 第一个非穷元所在列号，为其邻接点序号
	return -1;											// 否则无邻接点，返回-1
}


template <class DT>
bool InsertVex(MGraph<DT> &G,DT v)						// 插入值为v的顶点
{
	DT w;
	int j,weight;
	char ans;
	if(G.vexnum>=MAX_VEXNUM)							// 无存储空间，不能插入
	{
		cout<<"无存储空间，不能插入!"<<endl;
		return false;
	}
	G.vexs[G.vexnum++]= v;								// 顶点信息加入至G.vexs中，顶点数增1
	for(j=0;j<G.vexnum;j++)								// 初始化邻接矩阵最后一行和最后一列值
	{
		G.arcs[G.vexnum-1][j]=INF;
		G.arcs[j][G.vexnum-1]=INF;
	}
    cout<<"创建边吗（Y/N)?"<<endl;
	cin>>ans;
	while(ans=='Y'|| ans=='y')
	{
		cout<<"输入另一个顶点值和边的权值"<<endl;
		cin>>w>>weight;
		j=LocateVex(G,w);
		if(j>=0)										// 顶点存在
			InsertArc(G,v,w,weight);
		else
			cout<<w<<"顶点不存在！";
		cout<<"继续创建边吗（Y/N)?"<<endl;
		cin>>ans;
	};
	return true;	 
}

template <class DT>
bool InsertArc(MGraph<DT> &G,DT v,DT w,int weight)					// 在值为v、w顶点间加边 
{ 	int i = LocateVex(G,v);
	int j = LocateVex(G,w);
	if(i<0 || j<0 || i==j)								// 顶点不存在或两端点相同
	{
		cout<<"\n顶点不存在，或两顶点相同，不能插入！"<<endl;
		return false;									// 不能插入边，返回false
	}
	if(G.arcs[i][j]!=INF)
	{
		cout<<"\n边已存在，不能插入！"<<endl;
		return false;
	}
	G.arcs[i][j]=weight;
	G.arcs[j][i]=weight;
	G.arcnum++;
	return true;
}

template <class DT>
bool DeleteArc(MGraph<DT> &G,DT v,DT w)					// 按顶点值删除边
{
	int i = LocateVex(G,v);
	int j = LocateVex(G,w);
	if(i<0||j<0||i == j)								// 边不存在，返回false
	{
		cout<<"边不存在！"<<endl;						 
		return false;
	}
	G.arcs[i][j]=INF;									// 置邻接矩阵第 i 行第 j 列为无穷
	G.arcs[j][i]=INF;									// 置邻接矩阵第 i 列第 j 行为无穷
    G.arcnum--;											// 边数减1 
	return true;
}

template <class DT>
bool DeleteVex(MGraph<DT> &G,DT v)						// 按值删除顶点
{
	int i,j;
	DT w;
	i = LocateVex(G,v);									// 顶点定位
	if(i<0)
	{
		cout<<"顶点不存在！"<<endl;						// 顶点不存在
		return false;
	}
	for(j=0;j<G.vexnum;j++)								// 删除与顶点v相连的边
	{
		if(G.arcs[i][j]!=INF)
		{
			GetVex(G,j,w);
			DeleteArc(G,v,w);
		}
	}
	for(j=i+1;j<G.vexnum;j++)							// 排在顶点v后面的顶点前移
	{
		G.vexs[j-1] = G.vexs[j];
	}
	G.vexnum--;
	return true;
}


// 算法6.10 
template <class DT>
void DFS2(MGraph<DT> G,int v)							// 连通图深度优先遍历
{
	int w;
	visited[v] = true;									// 访问v
	cout<<G.vexs[v];
	for(w=0;w<G.vexnum;w++)								// 找v的未访问第1个邻接点
	{
		if(G.arcs[v][w]!=INF && !visited[w] )
		DFS2(G,w);
	}
	//cout<<endl;
}

// 算法6.9  
template <class DT>
void DFSTraverse(MGraph<DT> G)								// 非连通图深度优先遍历
{
	int i;
	for(i=0;i<G.vexnum;i++)									// 访问标志初始化
		visited[i]=0;
	for( i=0;i<G.vexnum;i++)								// 对未被访问的顶点
	{
		if(!visited[i])
			DFS2(G,i);										// 进行深度优先递归
	}
	cout<<endl;
	return ;
}

// 算法 6.11 												广度优先遍历 
template <class DT>
void BFS(MGraph<DT> G,int v)
{
	int w;
	LinkQueue<int> Q;										// 创建一个队列
	InitQueue(Q);
	cout<<G.vexs[v];										// 访问顶点v
	visited[v]=true;										// 做访问标志
	EnQueue(Q,v);											// 入队
	while(!QueueEmpty(Q))									// 队非空
	{
		DeQueue(Q,v);										// 出队
		for(w=FirstAdjvex(G,v);w>=0;w=NextAdjvex(G,v,w))	// 遍历v的邻接点
			if(!visited[w])									// 未被访问
			{
				cout<<G.vexs[w];							// 访问
				visited[w]=true;							// 做访问标志
				EnQueue(Q,w);								// 入队
			}
	} 
}

// 算法6.12 
template <class DT>
void BFSTraverse(MGraph<DT> G)								// 广度优先遍历
{
	int i;
	for(i=0;i<G.vexnum;i++)									// 访问标志初始化
		visited[i]=0;
	for(i=0;i<G.vexnum;i++)									// 对未被访问的结点
	{
		if(!visited[i])
			BFS(G,i);										// 进行BFS遍历
	}
	
}