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

2、邊的輸入順序施加某種限制。 請注意，生成樹的邊是有向邊，端點的順序不能反轉(zhuǎn)。5 .選擇內(nèi)容：(1) .根據(jù)堆棧類型(自己的定義和實現(xiàn))，用非遞歸算法實現(xiàn)深度優(yōu)先遍歷。(2) .把鄰接表做成記憶構(gòu)造，把深度優(yōu)秀的老師和廣度優(yōu)秀的老師做成樹，用凹陷的表和樹印刷成樹。2 .概要設計1 .為了實現(xiàn)上述功能，圖的抽象數(shù)據(jù)類型是必要的。 抽象數(shù)據(jù)類型的定義如下ADT圖形舉止數(shù)據(jù)對象V:V是具有相同特性的數(shù)據(jù)元素的集合，稱為頂點集。數(shù)據(jù)關系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 /最大頂點數(shù)typedef char VertexType20；類型枚舉 DG，DN，AG，an 圖形密鑰；enum BOOLFalse，True；3 .樹的結(jié)構(gòu)類型如下：typedef struct弧節(jié)點和矩陣的類型PPS； /VRType是圓弧的類型。 圖-0，1網(wǎng)-權(quán)重int *Info； /可以省略有關弧的信息的指針ArcCell，adj矩陣 max _ n max _ n ；typedef struct舉止VertexType vexsmax_n； /頂點adj矩陣arcs； /鄰接矩陣

4、int vexnum，arcnum； /頂點數(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 ) .樹模塊實現(xiàn)樹的抽象數(shù)據(jù)類型3 ) .掃描模塊實現(xiàn)樹的深度優(yōu)先掃描和寬度優(yōu)先掃描模塊間的調(diào)用關系如下主模塊木材模塊橫動模塊3 .詳細設計#包括 STD afx.h

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

6、ax_n； /頂點adj矩陣arcs； /鄰接矩陣int vexnum，arcnum； /頂點數(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 )舉止返回確認；以下/判斷隊列是否為空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；返回確認；以下/離開隊伍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；返回確認；以下/*頂點向量中的頂點定位*

8、/intlocate(mgrapgraph，VertexType v )舉止PS；for(i=0； iG.vexnumG.arcnum；請輸入cout 頂點： 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用鄰接矩陣表示，下標求v頂點的第一個鄰接點int i=0；while (I=g.vex num )返回- 1；電子返回I； 返回/v的第一個相鄰點的下標以下int NextAdjVex(MGraph G，int V，int w ) /圖g用鄰接矩陣表示int i=w 1；while(i=G.vexnum )返回- 1； /V的w鄰接點之后沒有鄰接點else返回I； 返回/v行w列之后的第一個非零元后綴以下int visited100； /*設置全局訪問標志數(shù)組*/PS PS (PK圖形g，PS v )從/編號v的頂點開始，通過深度優(yōu)先搜索對圖g進行掃描PS；visitedv=1；cout=0； w=下一個調(diào)整(g，v，w ) )舉止PS (！