/////////////////////////////////////////////////////////// 
//--------------------------------------------------------- 
//            基于邻接表实现图的基本运算
//--------------------------------------------------------- 
/////////////////////////////////////////////////////////// 

#include<stdio.h> 
#include<stdlib.h>
#include<malloc.h>
#include<string.h>
#include<ctype.h>
#include"queue.h"
#include<iostream>
using namespace std;

typedef int Status; //函数类型，其值为函数结果状态代码

//以下为函数运行结果状态代码 
#define TRUE 1
#define FALSE 0
#define OK 1 
#define ERROR 0 
#define INFEASIBLE -1 
#define OVERFLOW -2 
 
#define MAX_VERTEX_NUM 50
int visited[MAX_VERTEX_NUM];

typedef char VertexType;
typedef struct ArcNode {
	int adjvex;							//该弧所指向的顶点的位置
	ArcNode *nextarc;				//指向下一条弧的指针
	int info;							//该弧权值
}ArcNode,*arcNode;
typedef struct VNode {
	VertexType data;					//顶点信息
	ArcNode *firstarc;					//指向第一条依附该顶点的弧的指针
}VNode,*vNode,AdjList[MAX_VERTEX_NUM];
typedef struct {
	AdjList vertices;					//顶点集
	int vexnum,arcnum;					//图当前的顶点数和弧数
	int kind;							//图的种类标志,有向图，无向图，有向网，无向网
}AlGraph,*alGraph;						//图的结构

//-------------基本操作的函数原型说明----------------
Status CreateGraph(alGraph &G);					//构造图G
Status DestroyGraph(alGraph &G);				//销毁图G。
int LocateVex(alGraph G, vNode u);				//若u在图G中存在，返回顶点u的位置信息，否则返回其它信息
vNode FirstAdjVex(alGraph &G,vNode v);			//返回v的第一个邻接顶点，如果v没有邻接顶点，返回空
vNode NextAdjVex(alGraph &G, vNode v, vNode w);	//返回v的（相对于w）下一个邻接顶点，如果w是最后一个邻接顶点，返回空
Status InsertVex(alGraph &G,vNode v);			//在图G中增加新顶点v
Status DeleteVex(alGraph &G,vNode v);			//在图G中删除顶点v和与v相关的弧
Status InsertArc(alGraph &G,vNode v,vNode w);	//在图G中增加弧<v,w>，如果图G是无向图，还需要增加<w,v>
Status DeleteArc(alGraph &G,vNode v,vNode w);	//在图G中删除弧<v,w>，如果图G是无向图，还需要删除<w,v>
Status DFSTraverse(alGraph G);					//对图G进行深度优先搜索遍历
void DFSv(alGraph G,int ve);
Status BFSTraverse(alGraph G);					//对图G进行广度优先搜索遍历

//-----------基本操作的算法----------------
Status CreateGraph(alGraph &G){
	//构造图G
	G=(alGraph)malloc(sizeof(AlGraph));
	cout <<"请输入图的类型:"  <<endl;
	cout <<"0.有向图" <<endl;
	cout <<"1.无向图" <<endl;
	cout <<"2.有向网" <<endl;
	cout <<"3.无向网" <<endl;
	scanf("%d",&G->kind);
	getchar();
	int i,n,e,start,end;//n,e为顶点数和边数;start,end为边的起止序号
	int right=0;//权值
	arcNode p;
	printf("请输入顶点数和边数：");
	scanf("%d%d",&n,&e);
	getchar();
	G->vexnum=n;G->arcnum=e;
	for(i=0;i<n;i++){
		printf("请输入第%d个结点的数据：",i);
		scanf("%c",&G->vertices[i].data);
		getchar();
		G->vertices[i].firstarc=NULL;
	}
	for(i=0;i<e;i++){
		printf("请输入第%d条边的起止点序号：",i);
		scanf("%d%d",&start,&end);
		getchar();
		if(G->kind==2||G->kind==3){
			cout <<"请输入该边的权值:";
			scanf("%d",right);
			getchar();
		}
		p=(arcNode)malloc(sizeof(ArcNode));
		if(!p){
			printf("存储空间分配失败");
			exit(ERROR);
		}
		p->adjvex=end;
		p->info=right;
		p->nextarc=G->vertices[start].firstarc;
		G->vertices[start].firstarc=p;

		if(G->kind==1||G->kind==3){
			//如果图是无向的，则将边的反向再记录一次
			p=(arcNode)malloc(sizeof(ArcNode));
			if(!p){
				cout<<"存储空间分配失败";
				exit(ERROR);
			}
			p->adjvex=start;
			p->info=right;
			p->nextarc=G->vertices[end].firstarc;
			G->vertices[end].firstarc=p;
		}
	}
	if(G->kind==1||G->kind==3){
		G->arcnum*=2;
	}
	return OK;
}

Status DestroyGraph(alGraph &G){
	int i;
	arcNode p,q;
	for(i=0;i<G->vexnum;i++){
		p=G->vertices[i].firstarc;
		while(p){
			q=p->nextarc;
			free(p);
			p=q;
		}
	}
	free(G);
	return OK;
}

int LocateVex(alGraph G,vNode u){
	//若u在图G中存在，返回顶点u的位置信息，否则返回其它信息
	int i;
	for(i=0;i<G->vexnum;i++){
		if(u->data==G->vertices[i].data)
		return i;//存在返回位置
	}
	return -1;//不存在返回-1
}

vNode FirstAdjVex(alGraph &G,vNode v){
	//返回v的第一个邻接顶点，如果v没有邻接顶点，返回空
	vNode firstV=NULL;
	if(v->firstarc){
		firstV=&(G->vertices[v->firstarc->adjvex]);
	}
	return firstV;
}

vNode NextAdjVex(alGraph &G, vNode v, vNode w){
	//返回v的（相对于w）下一个邻接顶点，如果w是最后一个邻接顶点，返回空
	int locW=LocateVex(G,w);
	arcNode p=v->firstarc,nextp;
	while(p){
		if(p->adjvex==locW){
			if(p->nextarc){
				nextp=p->nextarc;
				return &(G->vertices[nextp->adjvex]);
			}
			else {
				return NULL;
			}
		}
		p=p->nextarc;
	}
/*	vNode nextV=NULL;
	arcNode firstC;
	int loc;
	if(v->firstarc){
		firstC=v->firstarc;
		if(firstC->nextarc){
			nextC=firstC->nextarc;
			loc=nextC->adjvex;
			return G->vertices[loc];
		}
		return NULL;
	}
	return NULL;*/
}

Status InsertVex(alGraph &G,vNode v){
	//在图G中增加新顶点v
	if(G->vexnum<MAX_VERTEX_NUM){//G的顶点数没到最大限度
		G->vertices[G->vexnum].data=v->data;
		G->vertices[G->vexnum].firstarc=NULL;
		G->vexnum++;
		return OK;
	}
	return ERROR;
}

Status DeleteVex(alGraph &G,vNode v){
	//
	int i,j;
	int loc=LocateVex(G,v);
	vNode tempV;
	arcNode tempA,ttempA;
	for(i=0;i<G->vexnum;i++){//删除所有指向v的弧
		if(i==loc){
			continue;
		}
		tempV=&(G->vertices[i]);
		tempA=tempV->firstarc;
		while(tempA){
			if(tempV->firstarc->adjvex==loc){
				//v是某个顶点的第一个邻接顶点
				tempV->firstarc=tempA->nextarc;
				free(tempA);
				G->arcnum--;
				break;
			}
			else {
				ttempA=tempA->nextarc;
				if(ttempA->adjvex==loc){
					tempA->nextarc=ttempA->nextarc;
					free(ttempA);
					G->arcnum--;
					break;
				}
			}
		}
	}
	tempV=&(G->vertices[loc]);
	tempA=tempV->firstarc;
	while(tempA){//删除所有v指向的弧
		ttempA=tempA->nextarc;
		free(tempA);
		G->arcnum--;
		tempA=ttempA;
	}
	tempV->firstarc=NULL;
	for(j=loc;j<G->vexnum-1;j++){
		G->vertices[j].data=G->vertices[j+1].data;
		G->vertices[j].firstarc=G->vertices[j+1].firstarc;
	}
	G->vexnum--;
	return OK;
}

Status InsertArc(alGraph &G,vNode v,vNode w){
	//在图G中增加弧<v,w>，如果图G是无向图，还需要增加<w,v>
	arcNode ep;
	ep=(arcNode)malloc(sizeof(ArcNode));
	int vi,wi;
	vi=LocateVex(G,v);//起点
	wi=LocateVex(G,w);//终点
	if(vi<0||wi<0||vi==wi){//至少有一个顶点不存在
		return ERROR;
	}
	if(G->kind==2||G->kind==3){//网
		cout <<"请输入该边的权值：";
		cin >> ep->info;
		getchar();
	}
	else {
		ep->info=0;
	}
	ep->adjvex=wi;
	ep->nextarc=G->vertices[vi].firstarc;
	G->vertices[vi].firstarc=ep;
	G->arcnum++;//边的数目加1
	if(G->kind==1||G->kind==3){//无向
		arcNode epp;
		epp=(arcNode)malloc(sizeof(ArcNode));
		epp->adjvex=vi;
		epp->info=ep->info;
		epp->nextarc=G->vertices[wi].firstarc;
		G->vertices[wi].firstarc=epp;
		G->arcnum++;
	}
	return OK;
}

Status DeleteArc(alGraph &G,vNode v,vNode w){
	//删除弧
	int vi,wi;
	arcNode p,q,pp,qq;
	vi=LocateVex(G,v);//起点
	wi=LocateVex(G,w);//终点
	if(vi<0||wi<0||vi==wi){
		return ERROR;
	}
	p=G->vertices[vi].firstarc;
	if(p->adjvex==wi){//第一条是目标弧
		G->vertices[vi].firstarc=p->nextarc;
		free(p);
		G->arcnum--;
		p=NULL;
	}
	else {
		while(p){//找到要删除的弧q
			q=p->nextarc;
			if(q->adjvex==wi){
				break;
			}
			p=p->nextarc;
			q=q->nextarc;
		}
		p->nextarc=q->nextarc;
		free(q);
		G->arcnum--;
	}

	if(G->kind==1||G->kind==3){//无向
		pp=G->vertices[wi].firstarc;
		if(pp->adjvex==vi){
			G->vertices[wi].firstarc=pp->nextarc;
			free(pp);
			G->arcnum--;
			pp=NULL;
		}
		else {
			while(pp){
				qq=pp->nextarc;
				if(qq->adjvex==vi){
					break;
				}
				pp=pp->nextarc;
				qq=qq->nextarc;
			}
			pp->nextarc==qq->nextarc;
			free(qq);
			G->arcnum--;
		}
	}
	return OK;
}

void DFSv(alGraph G,int ve){
	visited[ve]=1;
	cout << G->vertices[ve].data <<" ";
	arcNode eg=G->vertices[ve].firstarc;
	while(eg){
		if(!visited[eg->adjvex]){
			DFSv(G,eg->adjvex);
		}
		eg=eg->nextarc;
	}
}
Status DFSTraverse(alGraph G){
	//对图G进行深度优先搜索遍历
	int i;
	for(i=0;i<G->vexnum;i++){
		visited[i]=0;
	}
	for(i=0;i<G->vexnum;i++){
		if(!visited[i]){
			DFSv(G,i);
		}
	}
	return OK;
}

Status BFSTraverse(alGraph G){
	//对图G进行广度优先搜索遍历
	int i,j;
	arcNode p;
	SqQueue Q;
	for(i=0;i<G->vexnum;i++){
		visited[i]=0;
	}
	InitQueue(Q);

	for(i=0;i<G->vexnum;i++){
		if(!visited[i]){
			visited[i]=1;
			cout << G->vertices[i].data << ' ';
			EnQueue(Q,i);
			while(!QueueEmpty(Q)){
				DeQueue(Q,i);
				p=G->vertices[i].firstarc;

				while(p){
					if(!visited[p->adjvex]){
						visited[p->adjvex]=1;
						cout << G->vertices[p->adjvex].data << ' ';
						EnQueue(Q,p->adjvex);
					}
					p=p->nextarc;
				}
			}
		}
	}
}

int main(){
	alGraph G;
	vNode v,w;
	int op=1;
	while(op){
		system("cls");
		printf("\n\n");
		printf("\tMenu for Graph\n");
		printf("\t-------------------------------------------------\n");
		printf("\t\t1.CreateGraph\t\t2.DestroyGraph\n");
		printf("\t\t3.LocateVex\t\t4.FirstAdjVex\n");
		printf("\t\t5.NextAdjVex\t\t6.InsertVex\n");
		printf("\t\t7.DeleteVex\t\t8.InsertArc\n");
		printf("\t\t9.DeleteArc\t\t10.DFSTraverse\n");
		printf("\t\t11.BFSTraverse\t\t12.SaveFile\n");
		printf("\t\t13.ReadFile\t\t0.Exit\n");
		printf("\t-------------------------------------------------\n");
		printf("\t请选择你的操作[0~13]:");
		scanf("%d",&op);
		getchar();
		switch(op){
			case 1:
			{
				if(CreateGraph(G)){
					cout<<"创建图成功" <<endl;
				}
				else {
					cout<<"创建图失败" <<endl;
				}
				getchar();getchar();
			}
			break;
			case 2:
			{
				if(DestroyGraph(G)){
					cout<<"销毁图成功" <<endl;
				}
				else {
					cout<<"销毁图失败" <<endl;
				}
				getchar();getchar();
			}
			break;
			case 3:
			{
				int i,loc;
				vNode u;
				cout<<"请输入要查询的顶点的序号:";
				cin>>i;
				getchar();
				u=&G->vertices[i];//u为第i个顶点的指针
				loc=LocateVex(G,u);
				if(loc==-1){
					printf("地址为%d的结点u不在图G中\n",u);
				}
				else {
					printf("地址为%d的结点在图G中的位置是%d\n",u,loc);
				}
				getchar();getchar();
			}
			break;
			case 4:
			{
				int i;
				vNode v,u;
				cout<<"请输入要查找邻接顶点的顶点的序号：";
				cin>>i;
				getchar();
				v=&G->vertices[i];
				u=FirstAdjVex(G,v);
				if(u){
					cout<<"v的第一个邻接顶点的元素值是" << u->data <<endl;
				}
				else {
					cout<<"v没有邻接顶点" <<endl;
				}
				getchar();getchar();
			}
			break;
			case 5:
			{
				int i;
				vNode v,w,u;
				cout<<"请输入要查找下一个邻接顶点的顶点的序号：";
				cin>>i;
				getchar();
				v=&G->vertices[i];
				w=FirstAdjVex(G,v);
				u=NextAdjVex(G,v,w);
				if(u){
					cout<<"v相对于w的下一个邻接顶点元素值是" <<u->data <<endl;
				}
				else {
					cout<<"v没有相对于w的下一个邻接顶点" <<endl;
				}
				getchar();getchar();
			}
			break;
			case 6:
			{
				int statue;
				vNode v;
				v=(vNode)malloc(sizeof(VNode));
				cout<<"请输入要插入的顶点的数据：";
				cin>>v->data;
				getchar();
				statue=InsertVex(G,v);
				if(statue==OK){
					cout<<"插入成功"<<endl;
				}
				else{
					cout<<"插入失败"<<endl;
				}
				getchar();getchar();
			}
			break;
			case 7:
			{
				int i;
				vNode v;
				cout<<"请输入要删除的顶点的序号："<<endl;
				cin>>i;
				getchar();
				v=&G->vertices[i];
				if(DeleteVex(G,v)){
					cout<<"删除成功"<<endl;
				}
				else{
					cout<<"删除失败"<<endl;
				}
				getchar();getchar();
			}
			break;
			case 8:
			{
				int i,j;
				vNode v,w;
				cout<<"请输入要插入的边的起止顶点的序号："<<endl;
				cin>>i>>j;
				getchar();
				v=&G->vertices[i];
				w=&G->vertices[j];
				if(InsertArc(G,v,w)){
					cout<<"插入成功"<<endl;
				}
				else{
					cout<<"插入失败"<<endl;
				}
				getchar();getchar();
			}
			break;
			case 9:
			{
				int i,j;
				vNode v,w;
				cout<<"请输入要删除的边的起止顶点的序号："<<endl;
				cin>>i>>j;
				getchar();
				v=&G->vertices[i];
				w=&G->vertices[j];
				if(DeleteArc(G,v,w)){
					cout<<"删除成功"<<endl;
				}
				else{
					cout<<"删除失败"<<endl;
				}
				getchar();getchar();
			}
			break;
			case 10:
			{
				cout<<"图G深度优先搜索遍历："<<endl;
				DFSTraverse(G);
				cout<<endl<<"-----------The End------------"<<endl;
				getchar();getchar();
			}
			break;
			case 11:{
				cout<<"图G广度优先搜索遍历："<<endl;
				BFSTraverse(G);
				cout<<endl<<"-----------The End------------"<<endl;
				getchar();getchar();
			}
			break;
		}

	}
}