數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告 DFS和BFS算法

1、.（規(guī)格為A4紙或A3紙折疊）佛山科學(xué)技術(shù)學(xué)院（用四號(hào)宋體）實(shí) 驗(yàn) 報(bào) 告（用小二號(hào)黑體）課程名稱 數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn) 實(shí)驗(yàn)項(xiàng)目 實(shí)現(xiàn)DFS和BFS算法 專業(yè)班級(jí) 姓 名 學(xué) 號(hào) 指導(dǎo)教師 成 績 日 期 （用小四號(hào)宋體） 一、目的與要求1、通過本實(shí)驗(yàn)，掌握?qǐng)D，無向圖的基本概念，掌握?qǐng)D的遍歷。 2、掌握?qǐng)D的深度優(yōu)先搜索（DFS）與廣度優(yōu)先搜索（BFS）算法。二、實(shí)驗(yàn)原理圖的遍歷是圖的算法中一種非常重要的算法，通過建立圖的存儲(chǔ)結(jié)構(gòu)，采用深度優(yōu)先搜索與廣度優(yōu)先搜索算法可以進(jìn)行圖的遍歷。廣度優(yōu)先遍歷與深度優(yōu)先遍歷的區(qū)別在于：廣度優(yōu)先遍歷是以層為順序，將某一層上的所有節(jié)點(diǎn)都搜索到了之后才向下一層搜索；而深度

2、優(yōu)先遍歷是將某一條枝椏上的所有節(jié)點(diǎn)都搜索到了之后，才轉(zhuǎn)向搜索另一條枝椏上的所有節(jié)點(diǎn)。三、實(shí)驗(yàn)步驟1建立圖的存儲(chǔ)結(jié)構(gòu)。2輸入圖的基本接點(diǎn)與信息，完成初始化圖的工作。3完成圖的深度優(yōu)先搜索（DFS）和廣度優(yōu)先搜索算法，可以采用菜單形式進(jìn)行顯示與選擇。（可以在鍵盤輸入邊的信息以構(gòu)建一個(gè)無向圖。以（a,b）的形式輸入邊的信息；對(duì)此無向圖進(jìn)行深度優(yōu)先搜索，并輸出正確的序列。）4、 源代碼#include #include #define Max 20int visitedMax;struct queue/隊(duì)列的結(jié)構(gòu)體int *head;/指向所申請(qǐng)得到的空間的首地址int *front;/頭指針，若隊(duì)列

3、不為空，指向隊(duì)列頭元素int *rear;/尾指針，若隊(duì)列不空，指向隊(duì)列尾元素的下一個(gè)位置int stacksize;/當(dāng)前已分配的存儲(chǔ)空間s;/-圖的數(shù)組存儲(chǔ)表示-struct Mgraphchar vexsMax;int arcsMaxMax;int vexnum,arcnum;G;int Locatevex(char v)/確定v在G中的位置int i,t;for(i=0;iG.vexnum;i+)if(G.vexsi=v) t=i;return(t);/-采用數(shù)組表示法，構(gòu)造無向圖G-void CreateUDG()int i,j,k;char v1,v2;printf(請(qǐng)輸入頂點(diǎn)數(shù)和

4、弧數(shù)：);scanf(%d,%d,&G.vexnum,&G.arcnum);fflush(stdin);printf(請(qǐng)輸入%d個(gè)頂點(diǎn)n,G.vexnum);for(i=0;iG.vexnum;i+)printf(請(qǐng)輸入頂點(diǎn)%d: ,i);scanf(%c,&G.vexsi);fflush(stdin);for(i=0;iG.vexnum;i+)for(j=0;jG.vexnum;j+) G.arcsij=0;printf(請(qǐng)輸入%d條弧n,G.arcnum);for(k=0;kG.arcnum;k+)printf(請(qǐng)輸入弧%d: ,k);scanf(%c,%c,&v1,&v2);fflush

5、(stdin);i=Locatevex(v1);j=Locatevex(v2);G.arcsij=1;G.arcsji=1;/-返回v的第一個(gè)鄰接頂點(diǎn)-int Firstadjvex(int v)int i; for(i=0;iG.vexnum;i+)if(G.arcsvi=1) return(i);i=-1;return(i);/-返回v的(相對(duì)于w的）下一個(gè)鄰接頂點(diǎn)-int Nextadjvex(int v,int w)int i;for(i=0;iw) return(i);i=-1;return(i);/-從第v個(gè)頂點(diǎn)出發(fā)遞歸地深度優(yōu)先遍歷圖G-void DFS(int v) int w

6、;visitedv=1;printf(%c ,G.vexsv);for(w=Firstadjvex(v);w=0;w=Nextadjvex(v,w)if(!visitedw) DFS(w);/-對(duì)圖G作深度優(yōu)先遍歷-void Dfstraverse()int i;for(i=0;iG.vexnum;i+) visitedi=0;printf(深度優(yōu)先遍歷：);for(i=0;i=s.stacksize)/隊(duì)列滿，追加存儲(chǔ)空間s.head=(int *)realloc(s.head,(s.stacksize+10)*sizeof(int);if(!s.head) exit(0);/存儲(chǔ)分配失敗s

7、.stacksize+=10;*s.rear=e;s.rear+=1;void Dequeue(int u)/若隊(duì)列不空，則刪除s的隊(duì)頭元素u=*s.front;s.front+=1;/-按廣度優(yōu)先非遞歸遍歷圖G-void Bfstraverse()int v,u=0,w;for(v=0;vG.vexnum;v+) visitedv=0;Initqueue();printf(廣度優(yōu)先遍歷：);for(v=0;v=0;w=Nextadjvex(u,w)if(!visitedw)visitedw=1;printf(%c ,G.vexsw);Enqueue(w);printf(n);void mai

8、n()int i; printf（*n);printf(1.創(chuàng)圖n2.深度優(yōu)先搜索n3.廣度優(yōu)先搜索n4.退出n); printf(*n);printf(請(qǐng)選擇要操作的選項(xiàng)：);scanf(%d,&i);switch(i) case 1:CreateUDG();break;case 2:Dfstraverse();break;case 3:Bfstraverse();break;case 4:exit(0);main();5、 實(shí)驗(yàn)結(jié)果6、 思考題1圖的存儲(chǔ)方式有幾種？本實(shí)驗(yàn)中你會(huì)采用什么樣的存儲(chǔ)方式？答：圖的存儲(chǔ)方式有數(shù)組表示法、鄰接表、十字鏈表、鄰接多重表等4種常用存儲(chǔ)方式。本實(shí)驗(yàn)中我采用

9、了數(shù)組表示法存儲(chǔ)。 2、給出一幅無向圖G如下：V(G)=v1，v2，v3，v4，v5，v6，v7，v8 ，E(G)=(v1，v2)，(vl，v3)，(v2，v4)，(v2，v5)，(v3，v6)，(v3，v7)，（v1,v8），（v2,v8）1）請(qǐng)畫出示意圖；2）請(qǐng)根據(jù)你采用的存儲(chǔ)方式畫出存儲(chǔ)圖示； 3）在題目2的基礎(chǔ)上，請(qǐng)給出圖的深度優(yōu)先搜索序列；v1v4v24）在題目2的基礎(chǔ)上，請(qǐng)給出圖的廣度優(yōu)先搜索序列。v6 解：（1）v7v3v8v50 1 2 3 4 5 6 70 1 1 0 0 0 0 11 0 0 1 1 0 0 11 0 0 0 0 1 1 00 1 0 0 0 0 0 00 1 0 0 0 0 0 00 0 1 0 0 0 0 00 0 1 0 0 0 0 01 1 0 0 0 0 0 001234567 v1 v2 v3 v4 v5 v6 v7 v8 (2) (3)深度優(yōu)先搜索序列：a b d e h c f g (4)廣度優(yōu)先搜索序列：a b c