圖遍歷的演示

1、一、 需求分析1. 以鄰接表為存儲(chǔ)結(jié)構(gòu)，實(shí)現(xiàn)連通無向圖的深度優(yōu)先和廣度優(yōu)先遍歷。以用戶指定的結(jié)點(diǎn)為起點(diǎn)，分別輸出每種遍歷下的結(jié)點(diǎn)訪問序列和相應(yīng)生成樹的邊集。2. 每個(gè)結(jié)點(diǎn)用一個(gè)編號表示（如果一個(gè)圖有n個(gè)結(jié)點(diǎn)，則它們的編號分別為1,2,n）。通過輸入圖的全部邊輸入一個(gè)圖，每個(gè)邊為一個(gè)數(shù)對，可以對邊的輸入順序作出某種限制。注意，生成樹的邊是有向邊，端點(diǎn)順序不能顛倒。3. (1) 建立無向圖G的鄰接表表示。按照用戶輸入頂點(diǎn)數(shù),弧數(shù). 各邊(弧尾， 弧頭) (2) 輸出圖中邊的表示。用(A,B)表示 (3) 實(shí)現(xiàn)無向圖的深度優(yōu)先搜索遍歷。實(shí)現(xiàn)無向圖的廣度優(yōu)先搜索遍歷，使用輔助隊(duì)列q以存儲(chǔ)已經(jīng)被訪問的路

2、徑長度為1,2,的頂點(diǎn),并且訪問標(biāo)志數(shù)組visited,實(shí)現(xiàn)對圖的遍歷.4. 測試數(shù)據(jù)：輸入圖的頂點(diǎn)數(shù)和弧數(shù)：格式：頂點(diǎn)數(shù)，弧數(shù)； 輸入圖的頂點(diǎn)數(shù)和弧數(shù)：5，4 接著輸入各邊(弧尾，弧頭)： 5，3 3，1 1，2 2，4二、 概要設(shè)計(jì)1. 抽象數(shù)據(jù)類型圖的定義如下： ADT 數(shù)據(jù)對象V：V是具有相同特性的數(shù)據(jù)元素的集合，稱為頂點(diǎn)集。 數(shù)據(jù)關(guān)系R： R=VR VR=（v,w）|v,wV,(v,w)表示v和w之間存在路徑 基本操作P： CreateGraph(&G,V,VR)    初始條件：V是圖的頂點(diǎn)集，VR是圖中邊的集合。   &#

3、160;操作結(jié)果：按V和VR的定義構(gòu)造圖G。 DestroyGraph(&G)    初始條件：圖G存在。    操作結(jié)果：銷毀圖G。 LocateVex(G,u)    初始條件：圖G存在，u和G中頂點(diǎn)有相同特征。    操作結(jié)果：若G中存在頂點(diǎn)u，則返回該頂點(diǎn)在圖中位置；否則返回其他信息。 GetVex(G,v)    初始條件：圖G存在，v是G中某個(gè)頂點(diǎn)。    操作結(jié)果：返回v的信息。 FirstEd

4、ge(G,v)    初始條件：圖G存在，v是G中某個(gè)頂點(diǎn)。    操作結(jié)果：返回依附于v的第一條邊，若該頂點(diǎn)在G中沒有鄰接點(diǎn)，則返回“空”。 NextEdge(G,v,w)    初始條件：圖G存在，v是G中某個(gè)頂點(diǎn)，w是v的鄰接頂點(diǎn)。    操作結(jié)果：返回依附于v的（相對于w的）下一條邊。若不存在，則返回“空”。 InsertVex(&G,v)    初始條件：圖G存在，v和圖中頂點(diǎn)有相同特征。    操

5、作結(jié)果：在圖G中增添新頂點(diǎn)v。 DeleteVex(&G,v)    初始條件：圖G存在，v是G中某個(gè)頂點(diǎn)。    操作結(jié)果：刪除G中頂點(diǎn)v及其相關(guān)的邊。 2.   主程序 void main( ) 初始化；     用戶輸入信息:     接受用戶輸入的信息:     調(diào)用各個(gè)函數(shù);     輸出結(jié)果; 3. 本程序共有五個(gè)模塊

6、 創(chuàng)建圖的鄰接表表示的模塊輸出圖中邊的表示模塊深度優(yōu)先搜索遍歷圖的模塊廣度優(yōu)先搜索遍歷圖的模塊主程序模塊三、 詳細(xì)設(shè)計(jì)#include <dos.h>#include <conio.h>#include <stdio.h>#include <stdlib.h>#include <string.h>#define MAX_VERTEX_NUM 20 /圖的最大頂點(diǎn)數(shù)#define MAXQSIZE 30 /隊(duì)列的最大容量 enum BOOL False,True;typedef struct ArcNodeint adjvex; /該弧

7、所指向的頂點(diǎn)的位置struct ArcNode *nextarc; /指向下一條弧的指針ArcNode; /弧結(jié)點(diǎn)typedef structArcNode* AdjListMAX_VERTEX_NUM; /指向第一條依附該頂點(diǎn)的弧的指針int vexnum,arcnum; /圖的當(dāng)前頂點(diǎn)和弧數(shù) Graph; typedef struct /隊(duì)列結(jié)構(gòu)int elemMAXQSIZE; /數(shù)據(jù)域int front; /隊(duì)頭指針int rear; /隊(duì)尾指針SqQueue; BOOL visitedMAX_VERTEX_NUM; /全局變量訪問標(biāo)志數(shù)組void CreateGraph(Graph

8、&); /生成圖的鄰接表void DFSTraverse(Graph); /深度優(yōu)先搜索遍歷圖void DFS(Graph,int); void BFSTraverse(Graph); /廣度優(yōu)先搜索遍歷圖void Initial(SqQueue &); /初始化一個(gè)隊(duì)列BOOL QueueEmpty(SqQueue); /判斷隊(duì)列是否空BOOL EnQueue(SqQueue &,int); /將一個(gè)元素入隊(duì)列BOOL DeQueue(SqQueue &,int &); /將一個(gè)元素出隊(duì)列int FirstAdjVex(Graph,int); /求圖中

9、某一頂點(diǎn)的第一個(gè)鄰接頂點(diǎn)int NextAdjVex(Graph,int,int); /求某一頂點(diǎn)的下一個(gè)鄰接頂點(diǎn)void main()Graph G; /采用鄰接表結(jié)構(gòu)的圖char j='y'/-編者信息-printf("題目:編制一個(gè)“圖遍歷的演示”的程序.n");printf("班級:信息管理與信息系統(tǒng)01班.n");printf("姓名:徐麗n");printf("學(xué)號:201201050635n");printf("完成日期:2014.06.20n");/-/-程序解說

10、-printf("n本程序?qū)⒀菔旧梢粋€(gè)圖，并對它進(jìn)行遍歷.n");printf("輸入圖的頂點(diǎn)數(shù)和弧數(shù):n格式：頂點(diǎn)數(shù)，弧數(shù)；例如:5,4n");printf("接著輸入各邊(弧尾，弧頭):n例如:5,3n 3,1n 1,2n 2,4n");printf("程序會(huì)生成一個(gè)圖，并對它進(jìn)行深度和廣度遍歷.n");printf("深度遍歷:1->2->4->3->5n廣度遍歷:1->2->3->4->5n");/-while(j!='N'

11、;&&j!='n')printf("n請輸入頂點(diǎn)數(shù)和弧數(shù)：");scanf("%d,%d",&G.vexnum,&G.arcnum); /輸入圖的頂點(diǎn)數(shù)和弧數(shù)CreateGraph(G); /生成鄰接表結(jié)構(gòu)的圖DFSTraverse(G); /深度優(yōu)先搜索遍歷圖BFSTraverse(G); /廣度優(yōu)先搜索遍歷圖printf("圖遍歷完畢，繼續(xù)進(jìn)行嗎?(Y/N)");scanf(" %c",&j); void CreateGraph(Graph &G)

12、/構(gòu)造鄰接表結(jié)構(gòu)的圖Gint i;int start,end; ArcNode *s;for(i=1;i<=G.vexnum;i+) G.AdjListi=NULL; /初始化指針數(shù)組for(i=1;i<=G.arcnum;i+)scanf("%d,%d",&start,&end); /輸入弧的起點(diǎn)和終點(diǎn)s=(ArcNode *)malloc(sizeof(ArcNode); /生成一個(gè)弧結(jié)點(diǎn)s->nextarc=G.AdjListstart; /插入到鄰接表中s->adjvex=end;G.AdjListstart=s;s=(Arc

13、Node *)malloc(sizeof(ArcNode);s->nextarc=G.AdjListend;s->adjvex=start;G.AdjListend=s;void DFSTraverse(Graph G)/深度優(yōu)先遍歷圖Gint i;printf("深度優(yōu)先遍歷:");for(i=1;i<=G.vexnum;i+) visitedi=False; /訪問標(biāo)志數(shù)組初始化for(i=1;i<=G.vexnum;i+)if(!visitedi) DFS(G,i); /對尚未訪問的頂點(diǎn)調(diào)用DFSprintf("bb n")

14、;void DFS(Graph G,int i)/從第i個(gè)頂點(diǎn)出發(fā)遞歸地深度遍歷圖Gint w;visitedi=True; /訪問第i個(gè)頂點(diǎn)printf("%d->",i);for(w=FirstAdjVex(G,i);w>0;w=NextAdjVex(G,i,w)if(!visitedw) DFS(G,w); /對尚未訪問的鄰接頂點(diǎn)w調(diào)用DFSvoid BFSTraverse(Graph G)/按廣度優(yōu)先非遞歸的遍歷圖G，使用輔助隊(duì)列Q和訪問標(biāo)志數(shù)組visitedint i,u,w;SqQueue Q; printf("廣度優(yōu)先遍歷:")

15、;for(i=1;i<= G.vexnum;i+) visitedi=False; /訪問標(biāo)志數(shù)組初始化Initial(Q); /初始化隊(duì)列for(i=1;i<=G.vexnum;i+)if(!visitedi)visitedi=True; /訪問頂點(diǎn)iprintf("%d->",i);EnQueue(Q,i); /將序號i入隊(duì)列while(!QueueEmpty(Q) /若隊(duì)列不空，繼續(xù)DeQueue(Q,u); /將隊(duì)頭元素出隊(duì)列并置為ufor(w=FirstAdjVex(G,u);w>0;w=NextAdjVex(G,u,w)if(!visit

16、edw) /對u的尚未訪問的鄰接頂點(diǎn)w進(jìn)行訪問并入隊(duì)列visitedw=True;printf("%d->",w);EnQueue(Q,w);printf("bb n");int FirstAdjVex(Graph G,int v)/在圖G中尋找第v個(gè)頂點(diǎn)的第一個(gè)鄰接頂點(diǎn)if(!G.AdjListv) return 0;else return(G.AdjListv->adjvex);int NextAdjVex(Graph G,int v,int u)/在圖G中尋找第v個(gè)頂點(diǎn)的相對于u的下一個(gè)鄰接頂點(diǎn)ArcNode *p;p=G.AdjLis

17、tv;while(p->adjvex!=u) p=p->nextarc; /在頂點(diǎn)v的弧鏈中找到頂點(diǎn)uif(p->nextarc=NULL) return 0; /若已是最后一個(gè)頂點(diǎn)，返回0else return(p->nextarc->adjvex); /返回下一個(gè)鄰接頂點(diǎn)的序號void Initial(SqQueue &Q) /隊(duì)列初始化Q.front=Q.rear=0; BOOL QueueEmpty(SqQueue Q)/判斷隊(duì)列是否已空，若空返回True,否則返回Falseif(Q.front=Q.rear) return True;else r

18、eturn False;BOOL EnQueue(SqQueue &Q,int ch)/入隊(duì)列，成功返回True，失敗返回Falseif(Q.rear+1)%MAXQSIZE=Q.front) return False;Q.elemQ.rear=ch;Q.rear=(Q.rear+1)%MAXQSIZE;return True;BOOL DeQueue(SqQueue &Q,int &ch)/出隊(duì)列,成功返回True，并用ch返回該元素值，失敗返回Falseif(Q.front=Q.rear) return False;ch=Q.elemQ.front;Q.front=(Q.front+1)%MAXQSIZE;return True; /成功出隊(duì)列，返回True四、 調(diào)試分析2. 當(dāng)進(jìn)行圖中邊的表示輸出時(shí), 目的要驗(yàn)證輸入的邊是否正確表示, 但在程序中 是用指向頂點(diǎn)的指針表示, 結(jié)果只顯示出各個(gè)頂點(diǎn)的頂點(diǎn)編號, 后來調(diào)用鄰接表 的數(shù)組的頂點(diǎn)數(shù)據(jù)表示, 正常輸出. 3.  進(jìn)行有向圖的廣度優(yōu)先搜索時(shí), 開始只是簡單定義一個(gè)數(shù)組和兩個(gè)頭尾指針, 在進(jìn)行 數(shù)組插入與刪除時(shí)候只是移動(dòng)一下頭尾的指針,產(chǎn)生了錯(cuò)誤, 后來改