// 圖的遍歷_鄰接表存儲.cpp   檢驗深度優先和廣度優先的程序(鄰接表存儲表示)
#include<string.h>	//strcmp()
#include<malloc.h> 
#include<process.h>	//exit()
#include<iostream.h>	//cout,cin

typedef char VertexType[5]; // 頂點類型為字符串
 // 圖的鄰接表存儲表示
#define MAXV 20 //最大邊數

struct ArcNode // 表結點結構，省掉弧的相關信息（無權圖）
{
	int adjvex; // 該弧所指向的頂點的位置
	ArcNode *nextarc; // 指向下一條弧的指針
}; // 表結點

typedef struct VNode
{
	VertexType data;	// 頂點信息
	ArcNode *firstarc; // 第一個表結點的地址,指向第一條依附該頂點的弧的指針
}AdjList[MAXV]; // 頭結點

struct ALGraph
{
	AdjList vertices;
	int vexnum,arcnum; // 圖的當前頂點數和弧數
};
 
//與單鏈表的變量類型建立聯系
typedef ArcNode *LinkList; // 定義指向單鏈表結點的指針是指向圖的表結點的指針

int LocateVex(ALGraph G,VertexType u)
{ // 初始條件：圖G存在，u和G中頂點有相同特征
  // 操作結果：若G中存在頂點u，則返回該頂點在圖中位置；否則返回-1
	for(int i=0;i<G.vexnum;++i)
		if(strcmp(u,G.vertices[i].data)==0)
			return i;
		cout<<"無頂點"<<u<<endl;		//邊的頂點數據有誤
		exit(0);
}

void CreateGraph(ALGraph &G)
{ // 采用鄰接表存儲結構
	int i,j,k;
	VertexType vi,vj; // 連接邊或弧的2頂點
	cout<<"請輸入此圖的頂點數和邊數:";
	cin>>G.vexnum;	//讀入頂點數
	cin>>G.arcnum;	//讀入邊數
	cout<<"請輸入此圖所有頂點的編號:";
	for(i=0;i<G.vexnum;++i)		// 構造頂點向量
	{
		cin>>G.vertices[i].data;
		G.vertices[i].firstarc=NULL; // 初始化與該頂點有關的出弧鏈表
	}
	cout<<"請輸入此圖的有向邊(按照起點、終點依次輸入):\n";
	for(k=0;k<G.arcnum;++k) // 構造相關弧鏈表
	{
		cin>>vi;
		cin>>vj;
        i=LocateVex(G,vi);
        j=LocateVex(G,vj);
        ArcNode *p;
        p=(ArcNode *)malloc(sizeof(ArcNode));
        p->adjvex=j;
        p->nextarc=G.vertices[i].firstarc;
        G.vertices[i].firstarc=p;
	}
}

void Display(ALGraph G)
{ // 輸出圖的鄰接矩陣G
	int i;
	ArcNode *p;
	cout<<"該無向圖有"<<G.vexnum<<"個頂點:";
	for(i=0;i<G.vexnum;++i)
		cout<<G.vertices[i].data<<'\t';
	cout<<"\n該無向圖有"<<G.arcnum<<"條邊:\n";
	for(i=0;i<G.vexnum;i++)
	{
		p=G.vertices[i].firstarc;
		while(p)
		{
			if(i<p->adjvex) // 無向圖兩次中只顯示一次
			{ 
				cout<<G.vertices[i].data<<"-"<<G.vertices[p->adjvex].data<<endl;
			}
			p=p->nextarc;
		}
	}
	cout<<endl;
}

int visited[MAXV]; // 訪問標志數組(全局量)

void DFS(ALGraph G,int v)	//僅適用于鄰接表存儲結構(與算法7.5有不同)
{ // 從第v個頂點出發遞歸地深度優先遍歷圖G。
   int w;
   ArcNode *p;
   visited[v]=1;	 // 設置訪問標志為1(已訪問)
   cout<<G.vertices[v].data<<'\t'; // 訪問第v個頂點
   for(p=G.vertices[v].firstarc; p ;p=p->nextarc)
   {
	   w=p->adjvex;
	   if(!visited[w]) DFS(G,w); // 對v的尚未訪問的鄰接點w遞歸調用DFS
   }
}
void DFSTraverse(ALGraph G)
{ // 對圖G作深度優先遍歷。算法7.4
	int i;
	for(i=0;i<G.vexnum;i++)
		visited[i]=0; // 訪問標志數組初始化
	cout<<"深度優先搜索的結果:\n";
	for(i=0;i<G.vexnum;i++)
		if(!visited[i]) DFS(G,i); // 對尚未訪問的頂點調用DFS
		cout<<endl;
}

// 單鏈隊列－－隊列的鏈式存儲結構
typedef struct QNode
{
	int data;
	QNode *next;
}*QueuePtr;
struct LinkQueue
{
	QueuePtr front,rear; // 隊頭、隊尾指針
};

void InitQueue(LinkQueue &Q)
{ // 構造一個空隊列Q
	if(!(Q.front=Q.rear=new QNode)) exit(0);
	Q.front->next=NULL;
}
void EnQueue(LinkQueue &Q,int e)		//入隊
{ // 插入元素e為Q的新的隊尾元素
	QueuePtr p;
	if(!(p=new QNode)) exit(0);		// 存儲分配失敗
	p->data=e;
	p->next=NULL;
	Q.rear->next=p;
	Q.rear=p;
}
int DeQueue(LinkQueue &Q,int &e)	//出隊
{ // 若隊列不空，刪除Q的隊頭元素，用e返回其值，并返回OK，否則返回ERROR
	QueuePtr p;
	if(Q.front==Q.rear) return 0;
	p=Q.front->next;
	e=p->data;
	Q.front->next=p->next;
	if(Q.rear==p)
		Q.rear=Q.front;
	delete p;
	return 1;
}

void BFSTraverse(ALGraph G)
{   //按廣度優先非遞歸遍歷圖G。使用輔助隊列Q和訪問標志數組visited。算法
	int v,u,w;
	ArcNode *p;
	LinkQueue Q;
	for(v=0;v<G.vexnum;++v) visited[v]=0;		// 置初值(未訪問標志)
	InitQueue(Q);		// 置空的輔助隊列Q
	cout<<"廣度優先搜索的結果:\n";
	for(v=0;v<G.vexnum;v++) // 如果是連通圖，只v=0就遍歷全圖
		if(!visited[v]) // v尚未訪問
		{
			visited[v]=1;	//置已訪問標志
			cout<<G.vertices[v].data<<'\t';
			EnQueue(Q,v);	// v入隊列
			while(Q.front->next!=NULL) // 隊列不空
			{
				DeQueue(Q,u); // 隊頭元素出隊并置為u
				p=G.vertices[u].firstarc;
				while (p)
				{
					w=p->adjvex;
					if(!visited[w]) // w為u的尚未訪問的鄰接頂點
					{
						visited[w]=1;
						cout<<G.vertices[w].data<<'\t';
						EnQueue(Q,w); // w入隊
					}
					p=p->nextarc;
				}
			}
			cout<<"\n";
		}
}

void main()
{
	ALGraph g;
	CreateGraph(g); // 創建無向圖
	Display(g);		// 輸出無向圖
	DFSTraverse(g); // 調用算法7.4，有改動
	BFSTraverse(g); // 調用算法7.6，有改動
 }