/*題目：?
以鄰接表為存儲結構，實現連通無向圖的深度優先和廣度優先遍歷。以用戶指定的結點為起點，
分別輸出每種遍歷下的結點訪問序列和相應生成樹的邊集。
*/
#include
#include?
#include?
#include?
using?namespace?std;
int?visited[30];????????//全局數組記錄圖中節點訪問狀態
int?kvivj;
//=======================================鄰接表
#define?MAX_N?30
typedef?struct?ArcNode??//邊結點?
{?
	int?adjvex;?????????//該鄰接點在頂點數組中的下標
	struct?ArcNode?*nextarc;??//鏈域指向下一個鄰接點?
}ArcNode;
typedef?struct?VNode?????	//頂點結點
{	
	int	data;		????????//頂點信息?????????
	ArcNode?*firstarc;	???//邊鏈頭指針
}VNode?AdjList[MAX_N];???????//頂點數組（結構體數組）
typedef?struct
{???
	AdjList?vertices;??//鄰接表
	int?vexnumarcnum;???//頂點數和邊數
}ALGraph;

/****************************************************************************************
*函數名?：CreateGraph
*函數功能描述?：通過輸入邊的數對生成圖?
*函數參數?：ALGraph?&G
*函數返回值?：空?
*****************************************************************************************/
void?CreateGraph（ALGraph?&G）?{
	//?圖G用鄰接表表示創建圖
	cout<<“請輸入頂點數和邊數“<????cin>>G.vexnum>>G.arcnum;
	cout<<“輸入頂點序列“<????for（k?=?1;?k?<=?G.vexnum;?k++）
	{?
		cin>>G.vertices[k].data;?//輸入頂點序列
		G.vertices[k].firstarc?=?NULL;???//?初始化頭指針
	}
	printf（“===========================\n“）;
????for?（k?=?1;?k?<=?G.arcnum;?++k）
	{
????????printf（“輸入每條邊上的頂點序號:?“）;
????????scanf（“%d%d“&vi&vj）;

????????ArcNode?*pArcNode?=?（ArcNode*）malloc（sizeof（ArcNode））;
????????pArcNode->adjvex?=?vj;
????????pArcNode->nextarc?=?G.vertices[vi].firstarc;
????????G.vertices[vi].firstarc?=?pArcNode;

????????pArcNode?=?（ArcNode*）malloc（sizeof（ArcNode））;
????????pArcNode->adjvex?=?vi;
????????pArcNode->nextarc?=?G.vertices[vj].firstarc;
????????G.vertices[vj].firstarc?=?pArcNode;
????}????????												//讓vi，vj頂點都指向對方?
?????????
}??

/****************************************************************************************
*函數名?：DFS
*函數功能描述?：深度優先搜索遍歷圖G?
*函數參數?：G-遍歷的圖???v-出發頂點?
*函數返回值?：空?
*****************************************************************************************/

void?DFS（ALGraph?G??int?v）??{
??
????visited[v]?=?1;???????????????????//訪問后置為1?
??	cout<	ArcNode?*x?=?（ArcNode*）malloc（sizeof（ArcNode））;
	if（!x）???exit（-1）;???????????????//沒生成成功退出?
	x?=?G.vertices[v].firstarc;?
	int?w;?
	for?（;?x;?x?=?x->nextarc）?????//將x的鄰接點訪問?
	{?
		w?=?x->adjvex;??
		if（!visited[w]）?
			DFS（Gw）;?			//遞歸調用DFS?
	}
}



void?DFSB?（ALGraph?Gint?v）//深度搜索的邊集
{?
	visited[v]=1;?
	ArcNode?*y;?
	y=（ArcNode*）malloc（sizeof（ArcNode））;
	if（!y）?exit（-1）;
	y=G.vertices[v].firstarc;?
	int?u=G.vertices[v].data;?
	int?w;?
	for（;y;y=y->nextarc）
	{?
		w=y->adjvex;??
		if（visited[w]==0）
		{?
			cout<“<			DFSB（Gw）;??
		}?
	}
}
typedef?struct?QNode
{?
	int?data;
	QNode?*next;
}QNode*QueuePtr;
typedef?struct
{
	QueuePtr?front;?
	QueuePtr?rear;
}linkQueue;
void?InitQueue?（linkQueue?&Q）//建立一個空隊列
{?
	Q.front=Q.rear=（QueuePtr）malloc（sizeof（QNode