實驗四-圖的應(yīng)用——深度優(yōu)先／廣度優(yōu)先搜索遍歷.doc

《實驗四-圖的應(yīng)用——深度優(yōu)先／廣度優(yōu)先搜索遍歷.doc》由會員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在工程資料-天天文庫。

1、數(shù)據(jù)結(jié)構(gòu)實驗報告實驗四圖的應(yīng)用一、實驗題目：圖的應(yīng)用——深度優(yōu)先／廣度優(yōu)先搜索遍歷二、實驗內(nèi)容：很多涉及圖上操作的算法都是以圖的遍歷操作為基礎(chǔ)的。試編寫一個算法，實現(xiàn)圖的深度優(yōu)先和廣度優(yōu)先搜索遍歷操作。要求：以鄰接矩陣或鄰接表為存儲結(jié)構(gòu)，以用戶指定的頂點為起始點，實現(xiàn)連通無向圖的深度優(yōu)先及廣度優(yōu)先搜索遍歷，并輸出遍歷的結(jié)點序列。（注：學(xué)號為奇數(shù)的同學(xué)使用鄰接矩陣存儲結(jié)構(gòu)實現(xiàn)，學(xué)號為偶數(shù)的同學(xué)使用鄰接矩陣實現(xiàn)）提示：首先，根據(jù)用戶輸入的頂點總數(shù)和邊數(shù)，構(gòu)造無向圖，然后以用戶輸入的頂點為起始點，進(jìn)行深度優(yōu)先、廣度優(yōu)先

2、搜索遍歷，并輸出遍歷的結(jié)果。三、程序源代碼：#include#include#defineMAX_VERTEX_NUM20#defineOVERFLOW-1intvisited[80];typedefstructArcNode{intadjvex;//該弧所指向的頂點的位置structArcNode*nextarc;//指向下一條弧的指針}ArcNode;typedefstructVNode{intdata;//頂點信息ArcNode*firstarc;//指向第一條依附該頂

3、點的弧的指針}VNode,AdjList[MAX_VERTEX_NUM];typedefstruct{AdjListvertices;intvexnum,arcnum;//圖的當(dāng)前頂點數(shù)和弧數(shù)}ALGraph;typedefstructQNode{intdata;structQNode*next;}QNode,*QueuePtr;typedefstruct{QueuePtrfront;//隊頭指針QueuePtrrear;//隊尾指針}LinkQueue;voidInitQueue(LinkQueue&q){//

4、構(gòu)造一個空隊列qq.front=q.rear=(QueuePtr)malloc(sizeof(QNode));if(!q.front)exit(OVERFLOW);q.front->next=NULL;}voidEnQueue(LinkQueue&q,inte){//插入元素e為q的新的隊尾元素QueuePtrp;p=(QueuePtr)malloc(sizeof(QNode));if(!p)exit(OVERFLOW);//存儲分配失敗p->data=e;p->next=NULL;q.rear->next=p;

5、q.rear=p;}intDeQueue(LinkQueue&q){inte;//若隊列不空，則刪除q的隊頭元素，用e返回其值，并返回OK;否則返回ERRORif(q.front==q.rear)returnfalse;QueuePtrp;p=q.front->next;e=p->data;q.front->next=p->next;if(q.rear==p)q.rear=q.front;free(p);returne;}boolQueueEmpty(LinkQueue&q){//若隊列q為空隊列，則返回TRUE

6、，否則返回FLASEif(q.front==q.rear)returntrue;elsereturnfalse;}intLocateVex(ALGraphG,intv){inti;for(i=0;i

7、頂點信息:");for(i=0;i

8、->adjvex=j;s->nextarc=G.vertices[i].firstarc;G.vertices[i].firstarc=s;structArcNode*t;t=(ArcNode*)malloc(sizeof(ArcNode));t->adjvex=i;t->nextarc=G.vertices[j].firstarc;G.vertices[j].first