圖的遍歷試驗報告

本文格式為Word版，下載可任意編輯——圖的遍歷試驗報告數(shù)據(jù)結(jié)構(gòu)試驗報告計科101馮康202300814128

試驗圖的基本操作

一、試驗?zāi)康募耙?/p>

1、使學(xué)生1、使學(xué)生可以穩(wěn)定所學(xué)的有關(guān)圖的基本知識。2、熟練把握圖的存儲結(jié)構(gòu)。3、熟練把握圖的兩種遍歷算法。基本要求：

以鄰接表為存儲結(jié)構(gòu)，實現(xiàn)連通無向圖的深度優(yōu)先和廣度優(yōu)先遍歷。以用戶指定的結(jié)

點為起點，分別輸出每種遍歷下的結(jié)點訪問序列。

二、算法描述

[問題描述]

對給定圖，實現(xiàn)圖的深度優(yōu)先遍歷和廣度優(yōu)先遍歷。

由學(xué)生依據(jù)軟件工程的測試技術(shù)自己確定。

四、試驗報告要求

1、試驗報告要依照試驗報告格式規(guī)范書寫。2、試驗上要寫出多批測試數(shù)據(jù)的運行結(jié)果。3、結(jié)合運行結(jié)果，對程序進行分析。

編程思路：

深度優(yōu)先算法：計算機程序的一種編制原理，就是在一個問題出現(xiàn)多種可以實現(xiàn)的方法和技術(shù)的時候，應(yīng)當優(yōu)先選擇哪個更適合的，也是一種普遍的規(guī)律思想，此種思想在運算的過程中，用到計算機程序的一種遞歸的思想。

度優(yōu)先探尋算法：又稱廣度優(yōu)先探尋，是最簡便的圖的探尋算法之一，這一算法也是好多重要的圖的算法的原型。Dijkstra單源最短路徑算法和Prim最小生成樹算法都采用了和寬度優(yōu)先探尋類似的思想。其別名又叫BFS，屬于一種盲目搜尋法，目的是系統(tǒng)地展開并檢查圖中的所有節(jié)點，以找尋結(jié)果。換句話說，它并不考慮結(jié)果的可能位址，完全地探尋整張圖，直到找到結(jié)果為止。

以臨接鏈表作為存儲結(jié)構(gòu)，結(jié)合其存儲特點和上面兩種算法思想，給出兩種遍歷步驟：（1）既然圖中沒有確定的開始頂點，那么可從圖中任一頂點出發(fā)，不妨按編號的順序，先從編號小的頂點開始。

中原工學(xué)院計算機學(xué)院

打印時間：2023-3-26下午21:03

第1頁共4頁

數(shù)據(jù)結(jié)構(gòu)試驗報告計科101馮康202300814128

（2）要遍歷到圖中所有頂點，只需屢屢調(diào)用從某一頂點出發(fā)遍歷圖的算法。所以，下面只考慮從某一頂點出發(fā)遍歷圖的問題。

（3）為了在遍歷過程中便于區(qū)分頂點是否已經(jīng)被訪問，設(shè)置一個訪問標志數(shù)組visited[n]，n為圖中頂點的個數(shù)，其初值為0，當被訪問過后，其值被置為1。

（4）這就是遍歷次序的問題，圖的遍歷尋常有深度優(yōu)先遍歷和廣度優(yōu)先遍歷兩種方式，這兩種遍歷次序?qū)o向圖和有向圖都適用。

1、深度優(yōu)先遍歷從圖中某頂點v出發(fā)進行深度優(yōu)先遍歷的基本思想是：（1）訪問頂點v；

（2）從v的未被訪問的鄰接點中選取一個頂點w，從w出發(fā)進行深度優(yōu)先遍歷；（3）重復(fù)上述兩步，直至圖中所有和v有路徑相通的頂點都被訪問到。2、廣度優(yōu)先遍歷從圖中某頂點v出發(fā)進行廣度優(yōu)先遍歷的基本思想是：（1）訪問頂點v；

（2）依次訪問v的各個未被訪問的鄰接點v1，v2，……vk；

（3）分別從v1，v2，……vk出發(fā)依次訪問它們未被訪問的鄰接點，并使“先被訪問頂點的鄰接點〞先于“后被訪問頂點的鄰接點〞被訪問，直至圖中所有與頂點v有路徑的頂點都被訪問到。廣度優(yōu)先遍歷圖是以頂點v為起始點，由近至遠，依次訪問和v有路徑相通而且路徑長度為1，2，……的頂點。為了使“先被訪問頂點的鄰接點〞先于“后被訪問頂點的鄰接點〞被訪問，需設(shè)置隊列存儲訪問的頂點。五附錄

代碼解析：

#defineMAXVEX100intvisited[MAXVEX];intn;

structedgenode{

intadjvex;//臨接結(jié)點序號intinfo;//臨接結(jié)點信息edgenode*next;

中原工學(xué)院計算機學(xué)院

};連接結(jié)點的存儲類型

structvexnode{intdata;//結(jié)點信息intNo;edgenode*link;

打印時間：2023-3-26下午21:03

第2頁共4頁

數(shù)據(jù)結(jié)構(gòu)試驗報告

};數(shù)組結(jié)點類型

/*BFS遍歷時所需存儲類型*/structqueue{

計科101馮康202300814128

intfront,rear;edgenode**base;};

typedefvexnodeadjlist[MAXVEX];采用用戶交換模式來創(chuàng)立臨接鏈表：voidCreatGroup(adjlistprintf(\輸入結(jié)點(n)個數(shù)和邊(e)個數(shù):\for(inti=0;i\\n\\t起點序號，終點序號：\cin>>s>>d;//表示弧由s指向dedgenode*p=newedgenode;

/*每一個點的臨接結(jié)點沒有順序，為了插入p->adjvex便利每次插入結(jié)點都插入在臨接表的首位置，這樣后插入的結(jié)點反而在前面*/

p->adjvex=d;p->info=g[d].data;p->next=g[s].link;g[s].link=p;}}

voidDFS(adjlistg,intv){

visited[v]=0;printf(\遍歷過的結(jié)點用visited[v]=0進行標記edgenode*p=g[v].link;//查找連接結(jié)點while(p){

if(visited[p->adjvex])

DFS(g,p->adjvex);p=p->next;}}

/*廣度優(yōu)先探尋法(類似于樹的層次遍歷法)*/voidBFS(adjlistg,intv){visited[v]=0;

printf(\queueQ;

edgenode*p=g[v].link;

Q.base=newedgenode*[MAXVEX];Q.front=Q.rear=0;Q.base[Q.rear++]=p;

while(Q.front!=Q.rear){

visited[Q.base[Q.front]->adjvex]=0;

printf(\while(p){

if(visited[p->adjvex])Q.base[Q.rear++]=p;

中原工學(xué)院計算機學(xué)院

打印時間：2023-3-26下午21:03

第3頁共4頁

數(shù)據(jù)結(jié)構(gòu)試驗報告計科101馮康202300814128

p=p->next;}

p=g[Q.base[++Q.front]->adjvex].link;}}

心得體會：

數(shù)據(jù)結(jié)構(gòu)顧名思義講求的是一種存儲結(jié)構(gòu)，一路走來先后學(xué)習(xí)了表、樹，最終學(xué)習(xí)的是圖，對于每種存儲結(jié)構(gòu)學(xué)習(xí)之初都會學(xué)習(xí)一些基本操作，而操作之中又以創(chuàng)立和遍歷為最基本的操作，只有熟練把握了以后才能對其他操作進行研究和學(xué)習(xí)。

圖的存儲結(jié)構(gòu)相比表和樹都要繁雜，其操作過程也較難進行把握。僅僅是創(chuàng)立圖的存儲結(jié)構(gòu)便分為矩陣、臨接鏈表、十字鏈表等，對于每一種存儲結(jié)構(gòu)又分為有向與無向之分。然而，深度優(yōu)