圖的深度優(yōu)先遍歷和廣度優(yōu)先遍歷

1、華北水利水電學院 數(shù)據(jù)結構 實驗報告20 10 20 11 學年 第 一 學期 2008級 計算機 專業(yè)班級： 107 學號： 200810702 姓名： 王文波 實驗四 圖的應用一、 實驗目的：1掌握圖的存儲結構及其構造方法2掌握圖的兩種遍歷算法及其執(zhí)行過程二、 實驗內(nèi)容：以鄰接矩陣或鄰接表為存儲結構，以用戶指定的頂點為起始點，實現(xiàn)無向連通圖的深度優(yōu)先及廣度優(yōu)先搜索遍歷，并輸出遍歷的結點序列。提示：首先，根據(jù)用戶輸入的頂點總數(shù)和邊數(shù)，構造無向圖，然后以用戶輸入的頂點為起始點，進行深度優(yōu)先和廣度優(yōu)先遍歷，并輸出遍歷的結果。三、 實驗要求：1 各班學號為單號的同學采用鄰接矩陣實現(xiàn)，學號為雙號的同

2、學采用鄰接表實現(xiàn)。2 C/ C+完成算法設計和程序設計并上機調(diào)試通過。3 撰寫實驗報告，提供實驗結果和數(shù)據(jù)。4 寫出算法設計小結和心得。四、 程序源代碼：#include<iostream.h>#define MaxVerNum 50 struct edgenodeint endver;int inform;edgenode* edgenext; ;struct vexnode char vertex;edgenode* edgelink;struct Graph vexnode adjlistsMaxVerNum;int vexnum;int arcnum;/隊列的定義及相關函數(shù)

3、的實現(xiàn)struct QueueNodeint nData;QueueNode* next;struct QueueList QueueNode* front;QueueNode* rear;void EnQueue(QueueList* Q,int e)QueueNode *q=new QueueNode;q->nData=e;q->next=NULL;if(Q=NULL)return;if(Q->rear=NULL)Q->front=Q->rear=q;elseQ->rear->next=q;Q->rear=Q->rear->nex

4、t;void DeQueue(QueueList* Q,int* e)if (Q=NULL)return;if (Q->front=Q->rear)*e=Q->front->nData;Q->front=Q->rear=NULL;else*e=Q->front->nData;Q->front=Q->front->next;/創(chuàng)建圖void CreatAdjList(Graph* G)int i,j,k;edgenode* p1;edgenode* p2;cout<<"請輸入頂點數(shù)和邊數(shù):"<

5、<endl;cin>>G->vexnum>>G->arcnum;cout<<"開始輸入頂點表:"<<endl;for (i=0;i<G->vexnum;i+)cin>>G->adjlistsi.vertex;G->adjlistsi.edgelink=NULL;cout<<"開始輸入邊表信息:"<<endl;for (k=0;k<G->arcnum;k+)cout<<"請輸入邊<Vi,Vj&

6、gt;對應的頂點:"cin>>i>>j;p1=new edgenode;p1->endver=j;p1->edgenext=G->adjlistsi.edgelink;G->adjlistsi.edgelink=p1;p2=new edgenode;p2->endver=i;p2->edgenext=G->adjlistsj.edgelink;G->adjlistsj.edgelink=p2;/因為是無向圖，所以有兩次建立邊表的過程/-深度優(yōu)先遍歷void DFS(Graph *G,int i,int visit

7、)cout<<G->adjlistsi.vertex<<" "visiti=1;edgenode *p=new edgenode;p=G->adjlistsi.edgelink;if(G->adjlistsi.edgelink&&!visitp->endver)DFS(G,p->endver,visit);void DFStraversal(Graph *G,char c)/深度優(yōu)先遍歷cout<<"該圖的深度優(yōu)先遍歷結果為:"<<endl;int visitM

8、axVerNum;for(int i=0;i<G->vexnum;i+)visiti=0;/全部初始化為0，即未訪問狀態(tài)int m;for (i=0;i<G->vexnum;i+)if (G->adjlistsi.vertex=c)/根據(jù)字符查找序號m=i;DFS(G,i,visit);break;/繼續(xù)訪問未被訪問的結點for(i=0;i<G->vexnum;i+)if(visiti=0)DFS(G,i,visit);cout<<endl;/-廣度優(yōu)先遍歷void BFS(Graph* G,int v,int visit)QueueLis

9、t *Q=new QueueList;Q->front=Q->rear=NULL;EnQueue(Q,v);while(Q->rear!=NULL)int e=0;DeQueue(Q,&e);cout<<G->adjlistse.vertex<<" "visite=1;edgenode* p=new edgenode;p=G->adjlistse.edgelink;if(p)int m=p->endver;if(m=0)EnQueue(Q,m);while(visitm=0)p=p->edgenext

10、;if(p=NULL)break;m=p->endver;EnQueue(Q,m);void BFStraversal(Graph *G,char c)cout<<"該圖的廣度優(yōu)先遍歷結果為:"<<endl;int visitedMaxVerNum;for (int i=0;i<G->vexnum;i+)visitedi=0;int m;for (i=0;i<G->vexnum;i+)if (G->adjlistsi.vertex=c)m=i;BFS(G,i,visited);break;/繼續(xù)訪問未被訪問的結點f

11、or(i=0;i<G->vexnum;i+)if(visitedi=0)BFS(G,i,visited);cout<<endl;void main()Graph * G=new Graph;CreatAdjList(G);char ch;cout<<"請輸入開始遍歷的頂點:"cin>>ch;DFStraversal(G,ch);BFStraversal(G,ch);五、 程序運行情況（寫出輸入數(shù)據(jù)及運行結果）六、 小結（包括收獲、心得體會、存在的問題及解決問題的方法、建議等）注：內(nèi)容一律使用宋體五號字，單倍行間距本次試驗采用的

12、是鄰接表的方式實現(xiàn)圖的深度優(yōu)先遍歷和廣度優(yōu)先遍歷。對于深度優(yōu)先遍歷，主要是采用遞歸的方式，廣度優(yōu)先遍歷借助隊列來實現(xiàn)。試驗本身問題不是太大，但要注意輸入的問題，什么時候用空格，什么時候用回車，這一點是需要注意的，因為一旦數(shù)據(jù)的輸入有問題，結果當然也就不可能正確了。只有正確的輸入數(shù)據(jù)，建立圖，才能得出正確的遍歷結果。#include "stdio.h"#define MaxVerNum 50 struct edgenodeint endver;int inform;edgenode* edgenext; ;struct vexnode char vertex;edgenode

13、* edgelink;struct Graph vexnode adjlistsMaxVerNum;int vexnum;int arcnum;/隊列的定義及相關函數(shù)的實現(xiàn)struct QueueNodeint nData;QueueNode* next;struct QueueList QueueNode* front;QueueNode* rear;void EnQueue(QueueList* Q,int e)QueueNode *q=new QueueNode;q->nData=e;q->next=NULL;if(Q=NULL)return;if(Q->rear=NU

14、LL)Q->front=Q->rear=q;elseQ->rear->next=q;Q->rear=Q->rear->next;void DeQueue(QueueList* Q,int* e)if (Q=NULL)return;if (Q->front=Q->rear)*e=Q->front->nData;Q->front=Q->rear=NULL;else*e=Q->front->nData;Q->front=Q->front->next;/創(chuàng)建圖void CreatAdjList(

15、Graph* G)int i,j,k;edgenode* p1;edgenode* p2;printf("請輸入頂點數(shù)和邊數(shù):n");scanf("%d%d",&G->vexnum,&G->arcnum);printf("開始輸入頂點表:n");for (i=0;i<(G->vexnum);i+)fflush(stdin);/清空緩存scanf("%c",&G->adjlistsi.vertex);getchar();/吸收回車字符G->adjlistsi

16、.edgelink=NULL;printf("開始輸入邊表信息:n");for (k=0;k<G->arcnum;k+)printf("請輸入邊<Vi,Vj>對應的頂點:n");scanf("%d%d",&i,&j);p1=new edgenode;p1->endver=j;p1->edgenext=G->adjlistsi.edgelink;G->adjlistsi.edgelink=p1;p2=new edgenode;p2->endver=i;p2->e

17、dgenext=G->adjlistsj.edgelink;G->adjlistsj.edgelink=p2;/因為是無向圖，所以有兩次建立邊表的過程/-深度優(yōu)先遍歷void DFS(Graph *G,int i,int visit)printf("%c ",G->adjlistsi.vertex);visiti=1;edgenode *p=new edgenode;p=G->adjlistsi.edgelink;if(G->adjlistsi.edgelink&&!visitp->endver)DFS(G,p->e

18、ndver,visit);void DFStraversal(Graph *G,char c)/深度優(yōu)先遍歷printf("該圖的深度優(yōu)先遍歷結果為:");int visitMaxVerNum;for(int i=0;i<G->vexnum;i+)visiti=0;/全部初始化為0，即未訪問狀態(tài)int m;for (i=0;i<G->vexnum;i+)if (G->adjlistsi.vertex=c)/根據(jù)字符查找序號m=i;DFS(G,i,visit);break;/繼續(xù)訪問未被訪問的結點for(i=0;i<G->vexnum

19、;i+)if(visiti=0)DFS(G,i,visit);printf("n");/-廣度優(yōu)先遍歷void BFS(Graph* G,int v,int visit)QueueList *Q=new QueueList;Q->front=Q->rear=NULL;EnQueue(Q,v);while(Q->rear!=NULL)int e=0;DeQueue(Q,&e);printf("%c ",G->adjlistse.vertex);visite=1;edgenode* p=new edgenode;p=G->adjlistse.edgelink;if(p)int m=p->endver;if(m=0)EnQueue(Q,m);while(visitm=0)p=p->edgenext;if(p=NULL)break;m=p->endver;EnQueue(Q,m);void BFStraversal(Graph *G,char c)printf("該圖的廣度優(yōu)先遍歷結果為:");int visitedMaxVerNum;for (int i=0;i<G->vexnum;i+)visitedi=0;int m;for (i=0;i<G->