數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)四圖的應(yīng)用

1、華北水利水電學(xué)院 數(shù)據(jù)結(jié)構(gòu) 實(shí)驗(yàn)報(bào)告20 10 20 11 學(xué)年 第 一 學(xué)期 2008級(jí) 計(jì)算機(jī) 專業(yè)班級(jí)： 學(xué)號(hào)： 姓名： 實(shí)驗(yàn)四 圖的應(yīng)用一、 實(shí)驗(yàn)?zāi)康模?掌握?qǐng)D的存儲(chǔ)結(jié)構(gòu)及其構(gòu)造方法2掌握?qǐng)D的兩種遍歷算法及其執(zhí)行過程二、 實(shí)驗(yàn)內(nèi)容：以鄰接矩陣或鄰接表為存儲(chǔ)結(jié)構(gòu)，以用戶指定的頂點(diǎn)為起始點(diǎn)，實(shí)現(xiàn)無向連通圖的深度優(yōu)先及廣度優(yōu)先搜索遍歷，并輸出遍歷的結(jié)點(diǎn)序列。提示：首先，根據(jù)用戶輸入的頂點(diǎn)總數(shù)和邊數(shù)，構(gòu)造無向圖，然后以用戶輸入的頂點(diǎn)為起始點(diǎn)，進(jìn)行深度優(yōu)先和廣度優(yōu)先遍歷，并輸出遍歷的結(jié)果。三、 實(shí)驗(yàn)要求：1 各班學(xué)號(hào)為單號(hào)的同學(xué)采用鄰接矩陣實(shí)現(xiàn)，學(xué)號(hào)為雙號(hào)的同學(xué)采用鄰接表實(shí)現(xiàn)。2 c/ c+完成

2、算法設(shè)計(jì)和程序設(shè)計(jì)并上機(jī)調(diào)試通過。3 撰寫實(shí)驗(yàn)報(bào)告，提供實(shí)驗(yàn)結(jié)果和數(shù)據(jù)。4 寫出算法設(shè)計(jì)小結(jié)和心得。四、 程序源代碼：#includetypedef char vextype;const maxver=21;typedef struct listnode int adjvex; listnode* next; listnode;/表結(jié)點(diǎn) typedef struct vextype data; listnode *first;headnode;/頭結(jié)點(diǎn)typedef struct headnode vexsmaxver; int vexnum,arcnum; algraph;/圖void cr

3、eatealgraph(algraph &g) int i, s, d; listnode *p,*q; coutg.vexnumg.arcnum; for(i=1;i=g.vexnum;i+) coutn輸入第ig.vexsi.data; g.vexsi.first=null; /輸入第i個(gè)結(jié)點(diǎn)值并初始化第i個(gè)單鏈表為空 for(i=1; i=g.arcnum; i+) coutn輸入第isd;/s為始點(diǎn)，d為終點(diǎn) p=new listnode; p-adjvex=d; p-next=g.vexss.first; g.vexss.first=p; /將新建的以d為信息的表結(jié)點(diǎn)p插入s單鏈表的

4、頭結(jié)點(diǎn)后 q=new listnode; q-adjvex=s; q-next=g.vexsd.first; g.vexsd.first=q; /將新建的以s為信息的表結(jié)點(diǎn)q插入d單鏈表的頭結(jié)點(diǎn)后 int visitedmaxver;/定義全局?jǐn)?shù)組遍歷visitedvoid dfs(algraph g, int v)/被遍歷的圖g采用鄰接表作為存儲(chǔ)結(jié)構(gòu)，v為出發(fā)頂點(diǎn)編號(hào) listnode *p; coutadjvex=0) dfs(g,p-adjvex); /若p所指表結(jié)點(diǎn)對(duì)應(yīng)的鄰接頂點(diǎn)未訪問則遞歸地從該頂點(diǎn)出發(fā)調(diào)用dfs p=p-next; void dfstraverse(algraph

5、g) int v; /遍歷圖之前初始化各未訪問的頂點(diǎn) for(v=1; v=g.vexnum; v+) visitedv=0; /從各個(gè)未被訪問過的頂點(diǎn)開始進(jìn)行深度遍歷 for(v=1;v=g.vexnum;v+) if(visitedv=0) dfs(g,v);void bfs(algraph g, int v)/從頂點(diǎn)編號(hào)v出發(fā)，廣度遍歷鄰接表存儲(chǔ)的圖g int queuemaxver, front ,rear; listnode* p; front=rear=0; coutadjvex=0) v=p-adjvex; coutnext; void bfstraverse(algraph g) int v; /遍歷g以前，初始化visited數(shù)組為0 for(v=1;v=g.vexnum;v+) visitedv=0; for(v=1;v=g.vexnum;v+) if(visitedv=0) bfs(g,v);void main() algraph g; createalgraph(g); coutendl深度遍歷結(jié)果為：; dfstraverse(g); coutendl廣度遍歷結(jié)果為：; bfstraverse(g); coutendl;五、 程序運(yùn)行情況（寫出輸入數(shù)據(jù)及運(yùn)行結(jié)果）六、 小結(jié)（包括收獲、心得體會(huì)、存在的問題及解決問題的方法、建議等）本次實(shí)驗(yàn)是對(duì)