數(shù)據(jù)結(jié)構(gòu)實驗報告DFS和BFS算法

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

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

3、為空，指向隊列頭元素int *rear;/尾指針，若隊列不空，指向隊列尾元素的下一個位置int stacksize;/當(dāng)前已分配的存儲空間s;/-圖的數(shù)組存儲表示-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(請輸入頂點數(shù)和弧

4、數(shù)：);scanf(%d,%d,&g.vexnum,&g.arcnum);fflush(stdin);printf(請輸入%d個頂點n,g.vexnum);for(i=0;ig.vexnum;i+)printf(請輸入頂點%d: ,i);scanf(%c,&g.vexsi);fflush(stdin);for(i=0;ig.vexnum;i+)for(j=0;jg.vexnum;j+) g.arcsij=0;printf(請輸入%d條弧n,g.arcnum);for(k=0;kg.arcnum;k+)printf(請輸入弧%d: ,k);scanf(%c,%c,&v1,&v2);fflush(

5、stdin);i=locatevex(v1);j=locatevex(v2);g.arcsij=1;g.arcsji=1;/-返回v的第一個鄰接頂點-int firstadjvex(int v)int i; for(i=0;ig.vexnum;i+)if(g.arcsvi=1) return(i);i=-1;return(i);/-返回v的(相對于w的）下一個鄰接頂點-int nextadjvex(int v,int w)int i;for(i=0;iw) return(i);i=-1;return(i);/-從第v個頂點出發(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);/-對圖g作深度優(yōu)先遍歷-void dfstraverse()int i;for(i=0;ig.vexnum;i+) visitedi=0;printf(深度優(yōu)先遍歷：);for(i=0;i=s.stacksize)/隊列滿，追加存儲空間s.head=(int *)realloc(s.head,(s.stacksize+10)*sizeof(int);if(!s.head) exit(0);/存儲分配失敗s.

7、stacksize+=10;*s.rear=e;s.rear+=1;void dequeue(int u)/若隊列不空，則刪除s的隊頭元素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(請選擇要操作的選項：);scanf(%d,&i);switch(i) case 1:createudg();break;case 2:dfstraverse();break;case 3:bfstraverse();break;case 4:exit(0);main();5、 實驗結(jié)果6、 思考題1圖的存儲方式有幾種？本實驗中你會采用什么樣的存儲方式？答：圖的存儲方式有數(shù)組表示法、鄰接表、十字鏈表、鄰接多重表等4種常用存儲方式。本實驗中我采用了

9、數(shù)組表示法存儲。 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）請畫出示意圖；2）請根據(jù)你采用的存儲方式畫出存儲圖示； 3）在題目2的基礎(chǔ)上，請給出圖的深度優(yōu)先搜索序列；v1v4v24）在題目2的基礎(chǔ)上，請給出圖的廣度優(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