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

1、實(shí)驗(yàn)4 :圖的掃描主題：圖及其應(yīng)用圖的掃描班級：名稱：學(xué)校編號：完成日期：1 .需求分析1 .問題描述：與圖的操作有關(guān)的算法大多基于圖的掃描操作。 試制了在連接的無向圖表上演示訪問所有節(jié)點(diǎn)操作的程序。2 .基本要求：以鄰接表為記憶結(jié)構(gòu)，實(shí)現(xiàn)連通無向圖的深度優(yōu)先和寬度優(yōu)先遍歷。 以用戶指定的節(jié)點(diǎn)為起點(diǎn)，分別輸出各種掃描下的節(jié)點(diǎn)訪問序列和對應(yīng)的生成樹的邊緣集。3 .測試數(shù)據(jù)：教科書圖7.33。 暫時無視英里，出發(fā)點(diǎn)是北京。4 .實(shí)現(xiàn)提示：假設(shè)圖表中的節(jié)點(diǎn)不超過30個，并且每個節(jié)點(diǎn)由一個編號表示(如果圖表中有n個節(jié)點(diǎn)，則它們的編號分別為1、2、n )。 通過輸入圖的所有邊輸入圖，各邊一對一，可以對對

2、邊的輸入順序施加某種限制。 請注意，生成樹的邊是有向邊，端點(diǎn)的順序不能反轉(zhuǎn)。5 .選擇內(nèi)容：(1) .根據(jù)堆棧類型(自己的定義和實(shí)現(xiàn))，用非遞歸算法實(shí)現(xiàn)深度優(yōu)先遍歷。(2) .把鄰接表做成記憶構(gòu)造，把深度優(yōu)秀的老師和廣度優(yōu)秀的老師做成樹，用凹陷的表和樹印刷成樹。2 .概要設(shè)計1 .為了實(shí)現(xiàn)上述功能，圖的抽象數(shù)據(jù)類型是必要的。 抽象數(shù)據(jù)類型的定義如下ADT圖形舉止數(shù)據(jù)對象V:V是具有相同特性的數(shù)據(jù)元素的集合，稱為頂點(diǎn)集。數(shù)據(jù)關(guān)系r :R=VRVR= | v，wv且P(v，w )表示從v到w的弧，謂詞P(v，w )定義了弧的意思和信息 ADT圖形2 .這個抽象數(shù)據(jù)類型的常數(shù)如下：#define T

3、RUE 1#define FALSE 0#define OK 1#define max_n 20 /最大頂點(diǎn)數(shù)typedef char VertexType20；類型枚舉 DG，DN，AG，an 圖形密鑰；enum BOOLFalse，True；3 .樹的結(jié)構(gòu)類型如下：typedef struct弧節(jié)點(diǎn)和矩陣的類型PPS； /VRType是圓弧的類型。 圖-0，1網(wǎng)-權(quán)重int *Info； /可以省略有關(guān)弧的信息的指針ArcCell，adj矩陣 max _ n max _ n ；typedef struct舉止VertexType vexsmax_n； /頂點(diǎn)adj矩陣arcs； /鄰接矩陣

4、int vexnum，arcnum； /頂點(diǎn)數(shù)、邊數(shù)MGraph；/隊列類型定義typedef int QElemType；類型結(jié)構(gòu)qnode舉止QElemType data；結(jié)構(gòu)qnode * next；QNode、*QueuePtr；typedef struct舉止隊列ptr前端；隊列ptr rear；鏈接隊列；4 .本計劃包括三個模塊1 ) .主程序模塊void main ()舉止種樹深度優(yōu)先搜索掃描廣泛的優(yōu)先搜索以下2 ) .樹模塊實(shí)現(xiàn)樹的抽象數(shù)據(jù)類型3 ) .掃描模塊實(shí)現(xiàn)樹的深度優(yōu)先掃描和寬度優(yōu)先掃描模塊間的調(diào)用關(guān)系如下主模塊木材模塊橫動模塊3 .詳細(xì)設(shè)計#包括 STD afx.h

5、#includeusing namespace std；#define TRUE 1#define FALSE 0#define OK 1#define max_n 20 /最大頂點(diǎn)數(shù)typedef char VertexType20；類型枚舉 DG，DN，AG，an 圖形密鑰；enum BOOLFalse，True；typedef struct弧節(jié)點(diǎn)和矩陣的類型PPS； /VRType是圓弧的類型。 圖-0，1網(wǎng)-權(quán)重int *Info； /可以省略有關(guān)弧的信息的指針ArcCell，adj矩陣 max _ n max _ n ；typedef struct舉止VertexType vexsm

6、ax_n； /頂點(diǎn)adj矩陣arcs； /鄰接矩陣int vexnum，arcnum； /頂點(diǎn)數(shù)、邊數(shù)MGraph；/隊列的類型定義typedef int QElemType；類型結(jié)構(gòu)qnode舉止QElemType data；結(jié)構(gòu)qnode * next；QNode、*QueuePtr；typedef struct舉止隊列ptr前端；隊列ptr rear；鏈接隊列；/初始化隊列int init queue (鏈路隊列* q )舉止返回確認(rèn)；以下/判斷隊列是否為空int empty queue (鏈路隊列q )舉止PS (K.front=q.rear )返回真；else返回假；以下加入/行列i

7、nt enqueue (鏈路隊列* q，qelementtypee )舉止隊列ptr p；p-data=e；p-next=NULL；(*Q).rear-next=p；(*Q).rear=p；返回確認(rèn)；以下/離開隊伍int dequeue (鏈路隊列* q，qelementtype*e )舉止隊列ptr p；if (* q ).front=(* q ).rear )返回- 1；p=(*Q).front-next；*e=p-data；(*Q).front-next=p-next；if(*Q).rear=p )(*Q).rear=(*Q).front；刪除p；返回確認(rèn)；以下/*頂點(diǎn)向量中的頂點(diǎn)定位*

8、/intlocate(mgrapgraph，VertexType v )舉止PS；for(i=0； iG.vexnumG.arcnum；請輸入cout 頂點(diǎn)： for(k=0； kG.vexsk；for(i=0； 歡躍；歡躍；求出i=Locate(G，vi) j=Locate(G，vj) /vi和Vj的后綴g.arcs I .adj=1；g.arcs j .adj=1；以下以下第一次調(diào)整(m graph g，int V )/圖g用鄰接矩陣表示，下標(biāo)求v頂點(diǎn)的第一個鄰接點(diǎn)int i=0；while (I=g.vex num )返回- 1；電子返回I； 返回/v的第一個相鄰點(diǎn)的下標(biāo)以下int NextAdjVex(MGraph G，int V，int w ) /圖g用鄰接矩陣表示int i=w 1；while(i=G.vexnum )返回- 1； /V的w鄰接點(diǎn)之后沒有鄰接點(diǎn)else返回I； 返回/v行w列之后的第一個非零元后綴以下int visited100； /*設(shè)置全局訪問標(biāo)志數(shù)組*/PS PS (PK圖形g，PS v )從/編號v的頂點(diǎn)開始，通過深度優(yōu)先搜索對圖g進(jìn)行掃描PS；visitedv=1；cout=0； w=下一個調(diào)整(g，v，w ) )舉止PS (！