資源描述：
《實(shí)驗(yàn)四圖的應(yīng)用深度優(yōu)先／廣度優(yōu)先搜索遍歷》由會員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫。
1、華北水利水電學(xué)院數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報告2012～2013學(xué)年第一學(xué)期2010級計(jì)算機(jī)科學(xué)與技術(shù)專業(yè)班級：201013432學(xué)號：201013432姓名：蔡啟林實(shí)驗(yàn)四圖的應(yīng)用一、實(shí)驗(yàn)題目：圖的應(yīng)用——深度優(yōu)先／廣度優(yōu)先搜索遍歷二、實(shí)驗(yàn)內(nèi)容：很多涉及圖上操作的算法都是以圖的遍歷操作為基礎(chǔ)的。試編寫一個算法，實(shí)現(xiàn)圖的深度優(yōu)先和廣度優(yōu)先搜索遍歷操作。要求：以鄰接矩陣或鄰接表為存儲結(jié)構(gòu)，以用戶指定的頂點(diǎn)為起始點(diǎn)，實(shí)現(xiàn)連通無向圖的深度優(yōu)先及廣度優(yōu)先搜索遍歷，并輸出遍歷的結(jié)點(diǎn)序列。（注：學(xué)號為奇數(shù)的同學(xué)使用鄰接矩陣存儲結(jié)構(gòu)實(shí)現(xiàn)，學(xué)號為偶數(shù)的同學(xué)使用鄰接
2、矩陣實(shí)現(xiàn)）提示：首先，根據(jù)用戶輸入的頂點(diǎn)總數(shù)和邊數(shù)，構(gòu)造無向圖，然后以用戶輸入的頂點(diǎn)為起始點(diǎn)，進(jìn)行深度優(yōu)先、廣度優(yōu)先搜索遍歷，并輸出遍歷的結(jié)果。三、程序源代碼：#include#definemax100intvisited[max];typedefstructArcNode{intadjvex;structArcNode*nextarc;}ArcNode;typedefstructVNode{chardata;ArcNode*firstarc;}VNode,AdjList[max];typedefstruct
3、{AdjListvertices;intvexnum,arcnum;第7頁共7頁}ALGraph;typedefstructQNode{chardata;structQNode*next;}QNode,*QueuePtr;typedefstruct{QueuePtrfront;QueuePtrrear;}LinkQueue;intInitQueue(LinkQueue&Q){Q.front=Q.rear=newQNode;if(!Q.front)return0;Q.front->next=NULL;return1;}intQueue
4、Empty(LinkQueue&Q){if(Q.front==Q.rear)return1;elsereturn0;}intEnQueue(LinkQueue&Q,chare){QNode*p;p=newQNode;if(!p)return0;第7頁共7頁p->data=e;p->next=NULL;Q.rear->next=p;Q.rear=p;return1;}charDeQueue(LinkQueue&Q,int&e){QNode*p;if(Q.front==Q.rear)return0;p=Q.front->next;e=p
5、->data;Q.front->next=p->next;if(Q.rear==p)Q.rear=Q.front;delete(p);return1;}intLocateVex(ALGraphG,intv){inti;for(i=0;v!=G.vertices[i].data&&i=G.vexnum)return-1;returni;}voidCreatGraph(ALGraph&G){intk,i,j;ArcNode*p,*q;cout<<"請輸入頂點(diǎn)總數(shù)：";cin>>G.vexnum;第7
6、頁共7頁cout<<"請輸入邊數(shù)：";cin>>G.arcnum;charv1,v2;cout<<"輸入頂點(diǎn)信息：";for(i=0;i>G.vertices[i].data;G.vertices[i].firstarc=NULL;}cout<<"請輸入邊的信息"<>v1>>v2;i=LocateVex(G,v1);j=LocateVex(G,v2);p=newArcNode;q=newArcNode;p->adjvex=j;p
7、->nextarc=G.vertices[i].firstarc;G.vertices[i].firstarc=p;q->adjvex=i;q->nextarc=G.vertices[j].firstarc;G.vertices[j].firstarc=q;}}intFirstAdjVex(ALGraphG,intv){if(!G.vertices[v].firstarc)return0;returnG.vertices[v].firstarc->adjvex;}第7頁共7頁intNextAdjVex(ALGraphG,intv,i
8、ntw){ArcNode*p;p=G.vertices[v].firstarc;while(p&&p->adjvex!=w)p=p->nextarc;if(!p->nextarc)return-1;elsereturnp->nexta
