#include?
#include?
#include?
using?namespace?std;

#define?MAX_VERTEX_NUM?20??//頂點的最大數
#define?INIT_SIZE?100??????//堆棧的初始化大小
#define?INCREMENT?10???????//堆棧的增量
#define?OK?1
#define?ERROR?-1

//堆棧的存儲結構
typedef?struct{int?*top;int?*base;int?stacksize;}Stack;

//弧結點
typedef?struct?ArcNode{
	int?adjvex;
	struct?ArcNode?*nextarc;
	int?info;
}ArcNode*ArcPtr;

//頂點結點
typedef?struct?VNode{
	char?data;
	ArcNode?*firstarc;
	
}VNodeAdjList[MAX_VERTEX_NUM];

//圖的存儲結構
typedef?struct{
	AdjList?vertices;
	int?vexnumarcnum;
}ALGraph;

int?adjvex[MAX_VERTEX_NUM][MAX_VERTEX_NUM]={0};//各頂點的鄰接頂點

//確定頂點在圖中的位置
int?LocateVex（ALGraph?Gchar?ch）
{
	for（int?i=0;i		if（ch==G.vertices[i].data）?return?i;
		return?-1;
}

//創建圖
void?CreateGraph（ALGraph?&G）
{
	ArcNode?*p;	
	char?v1v2;int?*jinfo;
	int?mn;
	for（m=0;m		for（n=0;n			adjvex[m][n]=-1;
		cout<<“Enter?the?number?of?vertices?and?arcs:\n“;
		cin>>G.vexnum>>G.arcnum;
		j=new?int[G.vexnum];
		cout<<“Enter?the?vertices:\n“;
		for（int?i=0;i		{
			cin>>G.vertices[i].data;?
			G.vertices[i].firstarc=NULL;
			j[i]=0;
		}
		for（int?k=0;k		{
			p=new?ArcNode;
			cout<<“Enter?the?arcs:\n“;
			cin>>v1>>v2>>info;
			m=LocateVex（Gv1）;n=LocateVex（Gv2）;
			adjvex[m][j[m]++]=n;
			p->adjvex=n;
			p->info=info;
			p->nextarc=G.vertices[m].firstarc;
			G.vertices[m].firstarc=p;
		}
}

//輸出鄰接表
void?PrintTable（ALGraph?G）
{
	ArcNode?*p;
	cout<<“\n鄰接表:\n\n“;
	for（int?i=0;i	{
		cout<“;
		p=G.vertices[i].firstarc;
		while（p）
		{
			cout<adjvex<<“-“<info<<“-->“;
			p=p->nextarc;
		}
		cout<<“NULL“<	}
	cout<}

//深度優先遍歷圖========================================================
//第v個達頂點的第一個鄰接頂點
int?FirstAdjVex（ALGraph?Gint?v）
{
	int?w;
	w=adjvex[v][0];
	return?w;
}

int?pos（int?a[][MAX_VERTEX_NUM]int?vint?w）
{
	int?j;
	for（j=0;j	{
		if（a[v][j]==w）
			return?j;
	}
	return?-1;
}

//第v個頂點的下一個鄰接頂點
int?NextAdjVex（ALGraph?Gint?vint?w）
{
	int?n=pos（adjvexvw）;
	return?adjvex[v][n+1];
}

//*************************建立堆棧相關的函數*************************
void?InitStack（Stack?&S）
{
	S