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

#include<stdio.h> 
#include<stdlib.h>
#include<malloc.h>
#include<string.h>
#include<ctype.h>
#include"stack.h"

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 20
typedef struct ArcNode {
	int adjvex;							//该弧所指向的顶点的位置
	structArcNode *nextarc;				//指向下一条弧的指针
//	Infotype *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 CreateCraph(alGraph &G);					//按V和VR的定义构造图G
Status DestroyCraph(alGraph &G);				//销毁图G。
Status LocateVex(alGraph G,u);					//若u在图G中存在，返回顶点u的位置信息，否则返回其它信息
Status FirstAdjVex(alGraph &G, v);				//返回v的第一个邻接顶点，如果v没有邻接顶点，返回空
Status NextAdjVex(alGraph &G, v, w);			//返回v的（相对于w）下一个邻接顶点，如果w是最后一个邻接顶点，返回空
Status InsertVex(alGraph &G,v);					//在图G中增加新顶点v。
Status DeleteVex(alGraph &G,v);					//在图G中删除顶点v和与v相关的弧
Status InsertArc(alGraph &G,v,w);				//在图G中增加弧<v,w>，如果图G是无向图，还需要增加<w,v>
Status DeleteArc(alGraph &G,v,w);				//在图G中删除弧<v,w>，如果图G是无向图，还需要删除<w,v>
Status DFSTraverse(alGraph G);					//对图G进行深度优先搜索遍历，
Status BFSTraverse(alGraph G);					//对图G进行广度优先搜索遍历

//-----------基本操作的算法----------------
Status CreateCraph(alGraph &G){
	G=(alGraph)malloc(sizeof(AlGraph));
	int i,n,e,start,end;
	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();
		p=(arcNode)malloc(sizeof(ArcNode));
		if(!p){
			printf("存储空间分配失败");
			exit(ERROR);
		}
		p->adjvex=end;
		p->nextarc=G->vertices[start].firstarc;
		G->vertices[start].firstarc=p;
	}
	return OK;
}