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

2、先遍歷是將某一條枝椏上的所有節(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)行顯示與選擇。（可以在鍵盤(pán)輸入邊的信息以構(gòu)建一個(gè)無(wú)向圖。以（a,b）的形式輸入邊的信息；對(duì)此無(wú)向圖進(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)造無(wú)向圖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ì)列滿(mǎn)，追加存儲(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 main

8、()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、給出一幅無(wú)向圖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)畫(huà)出示意圖；2）請(qǐng)根據(jù)你采用的存儲(chǔ)方式畫(huà)出存儲(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