#include<iostream>
#include<queue>
#include<stack>
using namespace std;

#define INFINITY DBL_MAX     //无穷大
#define MAX_VERTEX_NUM 20 //最大顶点个数
enum GraphKind //图的类型
{
	DG,DN,UDG,UDN//有向图、有向网、无向图、无向网
};

//弧结构
typedef struct ArcCell
{
	double adj;//权值，无权图用1表示
}AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
//邻接矩阵图结构
 struct MGraph
{
	int vexs[MAX_VERTEX_NUM];//顶点集合
	AdjMatrix arecs;//邻接矩阵
	int vexnum,arcnum;//顶点数、弧数
	GraphKind kind;//图的类型
};


//表节点
 struct ArcNode
 {
	int adjvex;//弧的顶点位置
	ArcNode * nextarc;
	double adj;//弧的权值
 };
//头节点
 typedef struct VNode
 {
	int data;//顶点序号信息
	ArcNode * firstarc;
 }AdjList[MAX_VERTEX_NUM];
 //邻接表
 struct ALGraph
 {
	 int vexs[MAX_VERTEX_NUM];//顶点集合
	 AdjList vertices; //邻接链表
	 int vexnum,arcnum;//顶点数、弧数
	 int kind;//图的类型
 };

//显示主菜单
void ShowMainMenu()
{
	cout<<"\n";
	cout<<"  ***************图的基本操作及应用******************\n";
	cout<<"  *  1 无向图的基本操作及应用                      *\n";
	cout<<"  *  2 有向图的基本操作及应用                      *\n";
    cout<<"  *  3 无向网的基本操作及应用                      *\n";
	cout<<"  *  4 有向网的基本操作及应用                      *\n";
	cout<<"  *  5 退出                                        *\n";
	cout<<"  ***************************************************\n";
}
/*
*无向图的函数集
*/
//创建无向图的邻接矩阵
bool CreatUDG_M(MGraph & MG)
{
	MG.kind = UDG;
	cout<<"请输入该无向图的顶点个数、弧的条数："<<endl;
	cin>>MG.vexnum>>MG.arcnum;
	//初始化顶点集合
	cout<<"依次输入顶点序号"<<endl;
	for(int i = 0;i<MG.vexnum;i++)  cin>>MG.vexs[i];
	//初始化邻接矩阵
	for(int i = 0;i<MG.vexnum;i++)
	{
		for(int j = 0;j<MG.vexnum;j++)
		 {
			 MG.arecs[i][j].adj = INFINITY;
		 }
	}
	//构造邻接矩阵
	for(int i = 0;i<MG.arcnum;i++)
	{
		int v1,v2;
		cout<<"依次输入弧的两个顶点序号："<<endl;
		cin>>v1>>v2;
		int *p1 = find(MG.vexs,MG.vexs+MG.vexnum,v1);
		int *p2 = find(MG.vexs,MG.vexs+MG.vexnum,v2);
		if(p1==MG.vexs+MG.vexnum||p2==MG.vexs+MG.vexnum) return false;
		MG.arecs[(p1-MG.vexs)][(p2-MG.vexs)].adj = 1;
		//无向图的邻接矩阵是对称矩阵
		MG.arecs[(p2-MG.vexs)][(p1-MG.vexs)].adj = 1;
	}
	//输出该邻接矩阵
	cout<<"该邻接矩阵为（-1代表无穷大）："<<endl;
	for(int i = 0;i<MG.vexnum;i++)
	{
		for(int j = 0;j<MG.vexnum;j++)
	  {
		  if(MG.arecs[i][j].adj==INFINITY) cout<<"∞  ";
		  else
		  {
			  cout<<MG.arecs[i][j].adj<<"  ";
		  }
	  }
		cout<<endl;
	}
	return true;
}
//创建无向图的邻接表
bool CreatUDG_ALG(ALGraph & ALG)
{
	ALG.kind =  UDG;
	cout<<"请输入该无向图的顶点个数、弧的条数："<<endl;
	cin>>ALG.vexnum>>ALG.arcnum;
	//初始化顶点集合
	cout<<"依次输入顶点序号"<<endl;
	for(int i = 0;i<ALG.vexnum;i++)  cin>>ALG.vexs[i];
	//构造邻接表
	for(int i  = 0;i<ALG.vexnum;i++)
	{
	 //初始化头结点的data信息
		ALG.vertices[i].data = http://www.mamicode.com/ALG.vexs[i];>