#include
#define?exit?0?;
#define?MAX_VERTEX_NUM?20
typedef?int?InfoType??;
typedef?struct?ArcNode?{?????????????????????????//表結點
??int???????adjvex;??????????????????????????????//?該弧所指向的頂點的位置
??struct?ArcNode?*nextarc;???????????????????????//?指向下一條弧指針
??InfoType??info;????????????????????????????????//?該弧相關信息的指針
}?ArcNode;
typedef?char?VertexType?;
typedef?struct?VNode?{???????????????????????????//頭結點
?VertexType??data;???????????????????????????????//?頂點信息
??ArcNode??*firstarc;????????????????????????????//?指向第一條依附該頂點的弧
??}?VNode?AdjList[MAX_VERTEX_NUM];
typedef?struct?{?
????AdjList??vertices;
????int??vexnumarcnum;??????????????????????????//圖的當前頂點數和弧數
}ALGraph;
typedef?struct?QNode{
????VertexType??data;
??????struct?QNode?*next;
?????}?QNode*QueuePtr;
typedef?struct{
?????????QueuePtr?front;
?????????QueuePtr?rear;
????}linkQueue;?
?void?InitQueue（linkQueue??&Q）
??????????{
?????????????Q.front=Q.rear=new?QNode;
?????????????if（!Q.front）?exit（1）;
?????????????Q.front->next=NULL;
???????????}
void?EnQueue（linkQueue?&QVertexType?e）
{???????????????????????????????????????????????//?在當前隊列的尾元素之后，插入元素?e?為新的?隊列尾元素
QNode?*p;
p=new?QNode;
if（!p）exit（1）;??????????????????????????????????//?存儲分配失敗
p->data=e;
p->next=NULL;
Q.rear->next=p;?????????????????????????????????//?修改尾結點的指針
Q.rear=p;???????????????????????????????????????//?移動隊尾指針　
}
void?DeQueue（linkQueue?&QVertexType?&e）????????//?若隊列不空，則刪除當前隊列?Q?中的頭元素，用?e?返回其值，
????????????????????????????????????????????????//并返回?TRUE；否則返回?FALSE?
{
if（Q.front==Q.rear）exit（1）;?????????????????????//?鏈隊列中只有一個頭結點
QNode?*p;
p=Q.front->next;
e=p->data;??????????????????????????????????????//?返回被刪元素
Q.front->next=p->next;??????????????????????????//?修改頭結點指針
if（Q.rear==p）Q.rear=Q.front;
delete?p;???????????????????????????????????????//?釋放被刪結點
}????
void?CreateGraph?（ALGraph?&G）?{
int?headtail;
InfoType?weight;
cout<<“輸入頂點數和邊數“<????cin?>>?G.vexnum?>>?G.arcnum;????????????????//輸入頂點數和邊數
	cout<<“輸入各頂點的信息“<????for?（?int?i?=?0;?i?		//cout<<“輸入頂點“<????????cin?>>?G.?vertices[i].data;?????????????//輸入頂點信息
????????G.?ve