#include
#include
#include
#include

#define?TRUE?1
#define?FALSE?0
#define?OK?1
#define?ERROR?0

typedef?int?Status;
//=========================================================隊列定義
typedef?struct?Node
{
?int?elem;
?struct?Node?*next;
}Node*QNode;

typedef?struct
{
?QNode?front;
?QNode?rear;
}Queue;
//=======================================================圖的結構定義

#define?MAX?20

typedef?struct?ArcNode??????//表節點
{
?int?adjvex;?????????????//該邊所指向的頂點的位置
?struct?ArcNode?*nextarc;?//指向下一條邊
}ArcNode;

typedef?struct?VNode??????????//頭節點
{
?int?data;???????????????//頂點信息
?ArcNode?*firstarc;??????//指向第一條依附該節點的邊的指針
}VNodeAdjList[MAX];

typedef?struct
{
?AdjList?vertices;????//頭節點
?int?vexnum;??????????//節點的個數
?int?arcnum;??????????//邊的條數
}Graph;
//=================================================隊列函數

Status?InitQueue（Queue?*Q）
{
?Q->front=Q->rear=（QNode）malloc（sizeof（Node））;
?if（!Q->front）?exit（OVERFLOW）;
?Q->front->next=NULL;
?return?OK;
}
Status?EnQueue（Queue?*Qint?e）
{
?QNode?p=（QNode）malloc（sizeof（Node））;
?if（!p）?exit（OVERFLOW）;
?p->elem=e;
?p->next=NULL;
?Q->rear->next=p;
?Q->rear=p;
?return?OK;
}
Status?DeQueue（Queue?*Qint?*e）
{
?QNode?p;
?p=Q->front->next;
?Q->front->next=p->next;
?if（Q->rear==p）
??Q->rear=Q->front;
?*e=p->elem;
?free（p）;
?return?OK;
}

Status?QueueEmpty（Queue?Q）
{
?if（Q.rear==Q.front）
???return?TRUE;
?else
???return?FALSE;
}

//========================================================圖函數
int?LocateVex（Graph?*Gint?v）???//返回節點v在圖中的位置
{
	int?i;
	for（i=0;ivexnum;++i）
		if（G->vertices[i].data==v）//data表示頂點號
			break;
		else
			continue;
		if（ivexnum）
			return?i;
		else
			return?-1;//出錯
}

Status?CreateGraph（Graph?*G）
{//以鄰接表形式創建無向連通圖G
	int?mnijkv1v2flag=0;
	ArcNode?*p1*q1*p*q;
	printf（“輸入頂點數（小于20）:“）;
	scanf（“%d“&m）;
	printf（“輸入弧數:“）;
	scanf（“%d“&n）;
	G->vexnum=m;???????????//頂點數目
	G->arcnum=n;???????????//邊的數目
	for（i=0;ivexnum;++i）
	{
		G->vertices[i].data=i+1;?????//頂點信息，頂點賦值
		G->vertices[i].firstarc=NULL;
	}
????//==================================頂點信息
	printf（“各個虛擬節點:\n“）;
	for（i=0;ivexnum;++i）
		printf（“v%d\n“G->vertices[i].data）;
	for（k=0;karcnum;++k）
	{
		printf（“輸入第%d對弧頭弧尾:?“k+1）;
		scanf（“%d%d“&v1&v2）;
		i=LocateVex（Gv1）;//返回節點v1在圖中的位置
		j=LocateVex（Gv2）;//返回節點v2在圖中的位置
		if（i>=