實(shí)驗(yàn)四圖的遍歷

《實(shí)驗(yàn)四圖的遍歷》由會員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在學(xué)術(shù)論文-天天文庫。

1、人?沖誠以令實(shí)驗(yàn)報告學(xué)院（系）名稱：計算機(jī)與通信工程學(xué)院姓名氺氺氺學(xué)號專業(yè)計算機(jī)科學(xué)與技術(shù)（中外合作）班級2013級6班實(shí)驗(yàn)項(xiàng)目實(shí)驗(yàn)四：圖的遍歷課程名稱數(shù)據(jù)結(jié)構(gòu)課程代碼實(shí)驗(yàn)時間2014年12月110實(shí)驗(yàn)地點(diǎn)計算機(jī)基礎(chǔ)實(shí)驗(yàn)室210批改意見成績教師簽字：實(shí)驗(yàn)?zāi)康模豪斫鈭D的邏輯特點(diǎn)；掌握理解圖的兩種主要存儲結(jié)構(gòu)（鄰接矩陣和鄰接表），掌握圖的構(gòu)造、深度優(yōu)先遍歷、廣度優(yōu)先遍歷算法。具體實(shí)驗(yàn)題目：每位同學(xué)按丁述要求實(shí)現(xiàn)相應(yīng)算法：根據(jù)從鍵盤輸入的數(shù)據(jù)創(chuàng)建圖（圖的存儲結(jié)構(gòu)可采用鄰接矩陣或鄰接表），并對圖進(jìn)行深度優(yōu)先搜索和廣度優(yōu)先搜索（實(shí)驗(yàn)類型：驗(yàn)證型）1）問題描述：在主程序

2、中提供下列菜單：1...圖的建立2...深度優(yōu)先遍歷圖3...廣度優(yōu)先遍歷圖0...結(jié)束2）實(shí)驗(yàn)要求：圖的存儲可采用鄰接表或鄰接矩陣；定義下列過程：CreateGraphO：按從鍵盤的數(shù)據(jù)建立圖DFSGrahpO：深度優(yōu)先遍歷圖BFSGrahpO：廣度優(yōu)先遍歷圖【實(shí)驗(yàn)過程記錄(源程序、測試用例、測試結(jié)果及心得體會等)】實(shí)驗(yàn)源程序如下#include#include#defineMAX10//最大定點(diǎn)數(shù)typedefstructQNode//定義隊列{intdata;structQNode*next;}QNode;type

3、defstruct{QNode*front;QNode*rear;}Queue;typedefstructArcNode//連接表構(gòu)建圖{intadjvex;structArcNode*nextarc;}ArcNode;typedefstructVNode//頭結(jié)點(diǎn){chardata;ArcNode*firstarc;//鄰接鏈表頭指針}VNode;typedefstruct{VNodeadjlist[MAX];intv，a;//圖的頂點(diǎn)數(shù)和邊數(shù)}Graph;intInitQueue(Queue*s)//構(gòu)造一個空的對列{s->front=s->rear=(

4、QNode*)malloc(sizeof(QNode));if(!s->front)return(O);s->front->next=NULL;return1;}Enqueue(Queue*s,inte)//入隊列{QNode*p;p=(QNode*)malloc(sizeof(QNode));if(!p)return(O);p-〉data=e;p->next=NULL;s->rear->next=p;s->rear=p;return1;)DEQueue(Queueint*e)//出隊列{QNode*p;if(q->front==q->rear)retum1

5、;//表示這是空對歹ll{p=q-〉front-〉next;*e=p-〉data;//附值q-〉front-〉next=p-〉next;}if(q->rear==p)q->rear=q->front;free(p);return1;}intemptyQueue(Queue*q)//判斷隊列是否為空{(diào)if(q->front==q->rear)return1;elsereturn0;}voidCrerateGraph(Graph*G)//倉丨J建圖{inti，m，n;ArcNode*p;printf("請輸入圖的頂點(diǎn)數(shù)和邊數(shù):”);scanf(n%d%d’’，&

6、G-〉v，&G-〉a);getchar();printfC’請輸入。/od個頂點(diǎn)的信息二G-〉v);for(i=0;iv;i++){scanf("%s&G->adjlist[i].data);/*讀入頂點(diǎn)信息*/G->adjlist[i].firstarc=NULL;/*邊表置為空表*/}for(i=0;ia;i++){printf(”輸入第。/od條邊(起點(diǎn)序號，終點(diǎn)序號):"，i+1);scanf(M%d%dn，&m，&n);//輸入無序?qū)旤c(diǎn)編號0開始p=(ArcNode*)malloc(sizeof(ArcNode));p->adj

7、vex=n;p->nextarc=G->adjlist[m].firstarc;G-〉adjlist[m].firstarc=p;p=(ArcNode*)malloc(sizeof(ArcNode));p->adjvex=m;p->nextarc=G->adjlistfn].firstarc;G-〉adjIist[nl.firstarc=p;intvisitedrMAX];voidDFSGraph(GraphG，inti)//深度優(yōu)先遍歷{ArcNode*p;printf("訪問頂點(diǎn)：%c"，Gadjlist[i].data);/*訪問頂點(diǎn)i*/visi

8、ted[i]=l;p=G.adjli$t[i].fi