圖的應用______深度優(yōu)先_和_廣度優(yōu)先搜索遍歷

《圖的應用______深度優(yōu)先_和_廣度優(yōu)先搜索遍歷》由會員上傳分享，免費在線閱讀，更多相關內容在教育資源-天天文庫。

1、華##############學院數(shù)據(jù)結構實驗報告2011～2012學年第二學期2011級計算機專業(yè)班級：學號：姓名：實驗四圖的應用一、實驗題目：圖的應用——深度優(yōu)先／廣度優(yōu)先搜索遍歷二、實驗內容：很多涉及圖上操作的算法都是以圖的遍歷操作為基礎的。試編寫一個算法，實現(xiàn)圖的深度優(yōu)先和廣度優(yōu)先搜索遍歷操作。要求：以鄰接矩陣或鄰接表為存儲結構（學號為單號的同學以鄰接矩陣為存儲結構，雙號的同學以鄰接表為存儲結構）建立無向連通圖，從鍵盤上輸入指定的頂點為起始點，實現(xiàn)圖的深度優(yōu)先及廣度優(yōu)先搜索遍歷，并輸出遍歷的結點序列。提示：首先，根

2、據(jù)輸入的頂點總數(shù)和邊數(shù)，構造無向圖，然后以輸入的頂點為起始點，進行深度優(yōu)先、廣度優(yōu)先搜索遍歷，并輸出遍歷的結果。三、程序源代碼：#definemaxvex100#includetypedefstructedgenode{intadjvex;intvalue;edgenode*next;}ArcNode;typedefstructvexnode{chardata;ArcNode*firstarc;}VHeadNode;typedefstruct{intn,e;VHeadNodeadjlist[maxv

3、ex];第6頁共6頁}AdjList;intCreateAdjList(AdjList*g);voidshowAdjList(AdjList*g);voidBFS(AdjList*g,intvi);voidDFS(AdjList*g,intvi,intvisited[]);voidmain(){AdjListg;CreateAdjList(&g);}voidDFS(AdjList*g,intvi,intvisited[maxvex]){ArcNode*p;visited[vi]=1;cout<ad

4、jlist[vi].firstarc;while(p){if(visited[p->adjvex]==0)DFS(g,p->adjvex,visited);p=p->next;}}voidBFS(AdjList*g,intvi){inti,v,visited[maxvex];intqu[maxvex],front=0,rear=0;ArcNode*p;for(i=0;in;i++)visited[i]=0;visited[vi]=1;第6頁共6頁cout<

5、u[rear]=vi;while(front!=rear){front=(front+1)%maxvex;v=qu[front];p=g->adjlist[v].firstarc;while(p){if(visited[p->adjvex]==0){visited[p->adjvex]=1;cout<adjvex<<"";rear=(rear+1)%maxvex;qu[rear]=p->adjvex;}p=p->next;}}}//顯示創(chuàng)建的無向圖voidshowAdjList(AdjList*g){inti;Ar

6、cNode*p;cout<<"圖的鄰接表表示如下"<n;i++){第6頁共6頁cout<<"["<adjlist[i].data<<"]=>";p=g->adjlist[i].firstarc;while(p){cout<<"("<adjvex<<","<value<<")->";p=p->next;}cout<<"NULL"<

7、cNode*p,*q;g=newAdjList;cout<<"輸入頂點數(shù)（n），邊數(shù)（e）"<>g->n>>g->e;for(i=0;in;i++){cout<<"序號為"<>g->adjlist[i].data;g->adjlist[i].firstarc=NULL;}for(i=0;ie;i++){cout<<"序號為"<";cout<<"起點序號終點序號權值：";cin>>b>>t>>w;第6頁共6頁if(b<0

8、

9、b>g->n){

10、cout<<"輸入的節(jié)點不存在"<

11、

12、t>g->n){cout<<"輸入的節(jié)點不存在"<value=w;p->adjvex=t;p->next=g->adjlist[b].firstarc;g->ad