無(wú)向圖的存儲(chǔ)及深度和廣度優(yōu)先遍歷

《無(wú)向圖的存儲(chǔ)及深度和廣度優(yōu)先遍歷》由會(huì)員上傳分享，免費(fèi)在線(xiàn)閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫(kù)。

1、《數(shù)據(jù)結(jié)構(gòu)》實(shí)驗(yàn)報(bào)告◎?qū)嶒?yàn)題目:無(wú)序圖的存儲(chǔ)并分別實(shí)現(xiàn)深度和廣度優(yōu)先遍歷◎?qū)嶒?yàn)?zāi)康模豪斫獠⒄莆找脏徑颖淼姆绞酱鎯?chǔ)圖，以及圖的非遞歸的深度和廣度優(yōu)先遍歷◎?qū)嶒?yàn)內(nèi)容：首先將圖的元素輸入并以鄰接表的方式存儲(chǔ)，然后分別進(jìn)行遞歸和非遞歸遍歷。一、需求分析1、輸入的形式和輸入值的范圍：①輸入圖的頂點(diǎn)元素和邊；②輸入數(shù)字選擇要進(jìn)行的操作：深度遍歷，廣度遍歷或結(jié)束操作。2、輸出的形式:按深度或者廣度優(yōu)先順序輸出各節(jié)點(diǎn)的編號(hào)3、程序所能達(dá)到的功能：（1）以鄰接表的方式存儲(chǔ)圖（2）對(duì)圖進(jìn)行深度優(yōu)先的非遞歸遍歷（3）對(duì)

2、圖進(jìn)行廣度優(yōu)先的非遞歸遍歷4、測(cè)試數(shù)據(jù)：輸入各結(jié)點(diǎn)元素：a,b,c,d,e,f,g,h；輸入圖中的各邊：1,21,32,42,53,63,74,85,8操作選項(xiàng)輸入1進(jìn)行深度優(yōu)先遍歷；遍歷結(jié)果為：13762584操作選項(xiàng)輸入2進(jìn)行廣度優(yōu)先遍歷；遍歷結(jié)果為：1327654二概要設(shè)計(jì)（1）抽象數(shù)據(jù)類(lèi)型定義：#defineMaxVerNum100//邊表結(jié)點(diǎn)typedefstructnode{intadjvex;structnode*next;}EdgeNode,*ENode;頂點(diǎn)表結(jié)點(diǎn)；typedef

3、structvnode{charvertex;EdgeNode*firstedge;}VertexNode;typedefVertexNodeAdjList[MaxVerNum];定義圖；typedefstruct{AdjListadjlist;intn,e;}AlGraph;AlGraphG;（2）主程序的流程：1.根據(jù)提示輸入頂點(diǎn)個(gè)數(shù)和邊的個(gè)數(shù)；2.輸入圖的各邊；3.輸入數(shù)字執(zhí)行相關(guān)操作（3）其函數(shù)之間調(diào)用關(guān)系如下：main()模塊（開(kāi)始創(chuàng)建鏈表）Create（）創(chuàng)建圖輸入1輸入2按廣度優(yōu)先遍

4、歷按深度優(yōu)先遍歷輸入0結(jié)束操作執(zhí)行結(jié)束后，重新執(zhí)行判定操作和循環(huán)。三詳細(xì)設(shè)計(jì)1.元素類(lèi)型#defineMaxVerNum100typedefstructnode{intadjvex;structnode*next;}EdgeNode,*ENode;typedefstructvnode{charvertex;EdgeNode*firstedge;}VertexNode;typedefVertexNodeAdjList[MaxVerNum];typedefstruct{AdjListadjlist;i

5、ntn,e;}AlGraph;AlGraphG;2．每個(gè)模塊的分析：（1）主程序模塊：intmain(){inta,v;//創(chuàng)建圖Create(G);printf("請(qǐng)選擇要進(jìn)行的操作：選擇深度優(yōu)先請(qǐng)輸入1；選擇廣度優(yōu)先請(qǐng)輸入2；結(jié)束操作請(qǐng)輸入0");scanf("%d",&a);while(a!=0){printf("請(qǐng)輸入開(kāi)始遍歷頂點(diǎn)的坐標(biāo)");scanf("%d",&v);if(a==1)//深度優(yōu)先遍歷DfsTravel(G,v);}elseif(a==2)//廣度優(yōu)先

6、遍歷{BfsTravel(G,v);}printf("請(qǐng)選擇要進(jìn)行的操作：選擇深度優(yōu)先請(qǐng)輸入1；選擇廣度優(yōu)先請(qǐng)輸入2；結(jié)束操作請(qǐng)輸入0");scanf("%d",&a);}return0;}（2）深度優(yōu)先遍歷voidDfsTravel(AlGraph&G,intv){ENodestack[MaxVerNum];ENodep;intvisited[MaxVerNum],top=-1,i;for(i=0;i

7、：");printf("%d",v);visited[v]=1;p=G.adjlist[v].firstedge;while(top!=-1

8、

9、p!=NULL){while(p!=NULL){if(visited[p->adjvex]==1)p=p->next;else{printf("%d",p->adjvex);visited[p->adjvex]=1;top++;stack[top]=p;p=G.adjlist[p->adjvex].firstedge;}}if(top!=-1){p=s

10、tack[top];top--;p=p->next;}}printf("");}（3）廣度優(yōu)先遍歷voidBfsTravel(AlGraph&G,intv){intvisited[MaxVerNum];intqueue[MaxVerNum];intfront=-1,rear=-1;EdgeNode*p;inti;for(i=0;i