圖的遍歷實驗報告

1、實驗五 圖的基本操作一、實驗?zāi)康?、使學(xué)生可以鞏固所學(xué)的有關(guān)圖的基本知識。2、熟練掌握圖的存儲結(jié)構(gòu)。3、熟練掌握圖的兩種遍歷算法。二、實驗內(nèi)容問題描述對給定圖，實現(xiàn)圖的深度優(yōu)先遍歷和廣度優(yōu)先遍歷?；疽笠脏徑颖頌榇鎯Y(jié)構(gòu)，實現(xiàn)連通無向圖的深度優(yōu)先和廣度優(yōu)先遍歷。以用戶指定的結(jié)點為起點，分別輸出每種遍歷下的結(jié)點訪問序列?！緶y試數(shù)據(jù)】由學(xué)生依據(jù)軟件工程的測試技術(shù)自己確定。三、實驗前的準(zhǔn)備工作1、掌握圖的相關(guān)概念。2、掌握圖的邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)。3、掌握圖的兩種遍歷算法的實現(xiàn)。四、實驗報告要求1、實驗報告要按照實驗報告格式規(guī)范書寫。2、實驗上要寫出多批測試數(shù)據(jù)的運行結(jié)果。3、結(jié)合運行結(jié)果，對程序進(jìn)

2、行分析。編程思路：深度優(yōu)先算法：計算機程序的一種編制原理，就是在一個問題出現(xiàn)多種可以實現(xiàn)的方法和技術(shù)的時候，應(yīng)該優(yōu)先選擇哪個更合適的，也是一種普遍的邏輯思想，此種思想在運算的過程中，用到計算機程序的一種遞歸的思想。 度優(yōu)先搜索算法：又稱廣度優(yōu)先搜索，是最簡便的圖的搜索算法之一，這一算法也是很多重要的圖的算法的原型。Dijkstra單源最短路徑算法和Prim 最小生成樹算法都采用了和寬度優(yōu)先搜索類似的思想。其別名又叫BFS，屬于一種盲目搜尋法，目的是系統(tǒng)地展開并檢查圖中的所有節(jié)點，以找尋結(jié)果。換句話 說，它并不考慮結(jié)果的可能位址，徹底地搜索整張圖，直到找到結(jié)果為止。 以臨接鏈表作為存儲結(jié)構(gòu)，結(jié)合

3、其存儲特點和上面兩種算法思想，給出兩種遍歷步驟：（1）既然圖中沒有確定的開始頂點，那么可從圖中任一頂點出發(fā)，不妨按編號的順序，先從編號小的頂點開始。（2）要遍歷到圖中所有頂點，只需多次調(diào)用 從某一頂點出發(fā)遍歷圖的算法。所以，下面只考慮從某一頂點出發(fā)遍歷圖的問題。（3）為了在遍歷過程中便于區(qū)分頂點是否已經(jīng)被訪問，設(shè)置一個訪問標(biāo)志數(shù)組 visitedn，n為圖中頂點的個數(shù)，其初值為0，當(dāng)被訪問過后，其值被置為1。（4）這就是遍歷次序的問題，圖的遍歷通常有深度優(yōu)先遍歷和廣度優(yōu) 先遍歷兩種方式，這兩種遍歷次序?qū)o向圖和有向圖都適用。1、深度優(yōu)先遍歷    從圖中某頂點v出

4、發(fā)進(jìn)行深度優(yōu)先遍歷的基本思想是：（1）訪問頂點v；（2）從v的未被訪問的鄰接點中選取一個頂點w，從w出發(fā)進(jìn)行深度優(yōu)先遍歷；（3）重復(fù)上述兩步，直至圖中所有和v有路徑相通的頂點都被訪問到。2、廣度優(yōu)先遍歷    從圖中某頂點v出發(fā)進(jìn)行廣度優(yōu)先遍歷的基本思想是： （1）訪問頂點v；（2）依次訪問v的各個未被訪問的鄰接點v1，v2，vk；（3）分別從v1，v2，vk出發(fā)依次訪問它們未被訪問的鄰接點， 并使“先被訪問頂點的鄰接點”先于“后被訪問頂點的鄰接點”被訪問，直至圖中所有與頂點v有路徑的頂點都被訪問到。廣度優(yōu)先遍歷圖是以頂點v為起始點，由 近至遠(yuǎn)，依次訪問和v有路徑

5、相通而且路徑長度為1，2，的頂點。為了使“先被訪問頂點的鄰接點”先于“后被訪問頂點的鄰接點”被訪問，需設(shè)置隊列存儲 訪問的頂點。代碼解析：#define MAXVEX 100int visitedMAXVEX;int n;struct edgenode int adjvex;/臨接結(jié)點序號 int info; /臨接結(jié)點信息 edgenode*next;連接結(jié)點的存儲類型struct vexnode int data;/結(jié)點信息 int No; edgenode*link;數(shù)組結(jié)點類型/*BFS遍歷時所需存儲類型*/struct queue int front,rear; edgenode*b

6、ase;typedef vexnode adjlistMAXVEX;采用用戶交換模式來創(chuàng)建臨接鏈表：void CreatGroup(adjlist&g,int&n) int e,s,d; printf("輸入結(jié)點(n)個數(shù)和邊(e)個數(shù):"); cin>>n>>e; for(int i=0;i<n;i+)/創(chuàng)建結(jié)點數(shù)組 printf("n輸入第%d個結(jié)點信息No=",i); scanf("%d",&gi.data); gi.link=NULL; /*建立臨接鏈表，創(chuàng)建的是有向圖*/

7、 for(int i=0;i<e;i+) printf("第%d條邊=>nt起點序號，終點序號：",i+1); cin>>s>>d;/表示弧由s指向d edgenode*p=new edgenode; /*每一個點的臨接結(jié)點沒有順序，為了插入p->adjvex方便每次插入結(jié)點都插入在臨接表的首位置，這樣后插入的結(jié)點反而在前面*/ p->adjvex=d; p->info=gd.data; p->next=gs.link; gs.link=p; void DFS(adjlist g,int v) visitedv=0

8、; printf("%d=>",v);/遍歷過的結(jié)點用visitedv=0進(jìn)行標(biāo)記 edgenode*p=gv.link;/查找連接結(jié)點 while(p) if(visitedp->adjvex) DFS(g,p->adjvex); p=p->next; /*廣度優(yōu)先搜索法(類似于樹的層次遍歷法)*/void BFS(adjlist g,int v) visitedv=0; printf("%d=>",v); queue Q; edgenode*p=gv.link; Q.base=new edgenode*MAXVEX; Q

9、.front=Q.rear=0; Q.baseQ.rear+=p; while(Q.front!=Q.rear) visitedQ.baseQ.front->adjvex=0; printf("%d=>",Q.baseQ.front->adjvex); while(p) if(visitedp->adjvex) Q.baseQ.rear+=p; p=p->next; p=gQ.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)建和遍歷為最基本的操作，只有熟練掌握了以后才能對其他操作進(jìn)行研究和學(xué)習(xí)。圖的存儲結(jié)構(gòu)相比表和樹都要復(fù)雜，其操作過程也較難進(jìn)行掌握。僅僅是創(chuàng)建圖的存儲結(jié)構(gòu)便分為矩陣、臨接鏈表、十字