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

試驗(yàn)圖的基本操作

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

1、使學(xué)生1、使學(xué)生可以穩(wěn)定所學(xué)的有關(guān)圖的基本知識(shí)。2、熟練把握?qǐng)D的存儲(chǔ)結(jié)構(gòu)。3、熟練把握?qǐng)D的兩種遍歷算法?；疽螅?/p>

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

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

二、算法描述

[問題描述]

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

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

四、試驗(yàn)報(bào)告要求

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

編程思路：

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

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

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

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

打印時(shí)間：2023-3-26下午21:03

第1頁共4頁

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

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

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

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

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

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

（2）依次訪問v的各個(gè)未被訪問的鄰接點(diǎn)v1，v2，……vk；

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

代碼解析：

#defineMAXVEX100intvisited[MAXVEX];intn;

structedgenode{

intadjvex;//臨接結(jié)點(diǎn)序號(hào)intinfo;//臨接結(jié)點(diǎn)信息edgenode*next;

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

};連接結(jié)點(diǎn)的存儲(chǔ)類型

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

打印時(shí)間：2023-3-26下午21:03

第2頁共4頁

數(shù)據(jù)結(jié)構(gòu)試驗(yàn)報(bào)告

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

/*BFS遍歷時(shí)所需存儲(chǔ)類型*/structqueue{

計(jì)科101馮康202300814128

intfront,rear;edgenode**base;};

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

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

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é)點(diǎn)用visited[v]=0進(jìn)行標(biāo)記edgenode*p=g[v].link;//查找連接結(jié)點(diǎn)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é)院計(jì)算機(jī)學(xué)院

打印時(shí)間：2023-3-26下午21:03

第3頁共4頁

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

p=p->next;}

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

心得體會(huì)：

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

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