圖的應(yīng)用——深度優(yōu)先遍歷和廣度優(yōu)先遍歷.doc

華北水利水電大學(xué) 數(shù)據(jù)結(jié)構(gòu) 實(shí)驗(yàn)報(bào)告20132014學(xué)年 第 二 學(xué)期 2013級(jí) 計(jì)算機(jī)科學(xué)與技術(shù)（專升本） 專業(yè)班級(jí)： 學(xué)號(hào)： 姓名： 實(shí)驗(yàn)四 圖的應(yīng)用一、 實(shí)驗(yàn)題目：圖的應(yīng)用深度優(yōu)先廣度優(yōu)先搜索遍歷二、 實(shí)驗(yàn)內(nèi)容：很多涉及圖上操作的算法都是以圖的遍歷操作為基礎(chǔ)的。試編寫(xiě)一個(gè)算法，實(shí)現(xiàn)圖的深度優(yōu)先和廣度優(yōu)先搜索遍歷操作。要求：以鄰接矩陣或鄰接表為存儲(chǔ)結(jié)構(gòu)，以用戶指定的頂點(diǎn)為起始點(diǎn)，實(shí)現(xiàn)連通無(wú)向圖的深度優(yōu)先及廣度優(yōu)先搜索遍歷，并輸出遍歷的結(jié)點(diǎn)序列。（注：學(xué)號(hào)為奇數(shù)的同學(xué)使用鄰接矩陣存儲(chǔ)結(jié)構(gòu)實(shí)現(xiàn)，學(xué)號(hào)為偶數(shù)的同學(xué)使用鄰接矩陣實(shí)現(xiàn)）提示：首先，根據(jù)用戶輸入的頂點(diǎn)總數(shù)和邊數(shù)，構(gòu)造無(wú)向圖，然后以用戶輸入的頂點(diǎn)為起始點(diǎn)，進(jìn)行深度優(yōu)先、廣度優(yōu)先搜索遍歷，并輸出遍歷的結(jié)果。三、程序源代碼：#include#include#include#define MAX_VERTEX_NUM 20typedef struct ArcCell int adj;ArcCell,AdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM;typedef struct char vexsMAX_VERTEX_NUM;AdjMatrix arcs;int vexnum,arcnum;MGraph;typedef struct Queue char* front;char* rear;Queue;bool visitedMAX_VERTEX_NUM=false;void InitQueue(Queue &Q) /初始化隊(duì)列Q.front = Q.rear = (char *)malloc(MAX_VERTEX_NUM * sizeof(char);if (!Q.front)exit(0);void EnQueue(Queue &Q,char v) /入隊(duì)列*Q.rear = v;Q.rear +;void DeQueue(Queue &Q,char &u) /出隊(duì)列u = *Q.front;Q.front +;bool QueueEmpty(Queue Q) /判定隊(duì)列是否為空if (Q.rear - Q.front)return false;return true; int LocateVex(MGraph G,char v) /找出頂點(diǎn)v在圖G中的位置并返回for (int i = 0; i G.vexnum; i +) if (v = G.vexsi)return i;int CreateUNG(MGraph &G) int i,j,k;char v1,v2;printf(輸入圖的頂點(diǎn)個(gè)數(shù)和弧的個(gè)數(shù)(用空格作為間隔):);scanf(%d %d,&G.vexnum,&G.arcnum);/輸入圖的頂點(diǎn)個(gè)數(shù)和弧的個(gè)數(shù)printf(開(kāi)始輸入頂點(diǎn)的值n);getchar();for ( i = 0; i G.vexnum; i +) printf(輸入第%d個(gè)頂點(diǎn)的值:,i + 1);scanf(%c,&G.vexsi);/輸入頂點(diǎn)值getchar();for (i = 0; i G.vexnum; i +) /初始化鄰接矩陣for (j = 0; j G.vexnum; j +)G.arcsij.adj = 0;/鄰接矩陣結(jié)束printf(輸入弧關(guān)聯(lián)的頂點(diǎn)（兩個(gè)頂點(diǎn)之間用空格作為間隔）n);for (k = 0; k G.arcnum; k +) printf(輸入第%d條弧關(guān)聯(lián)的頂點(diǎn):,k + 1);scanf(%c %c,&v1,&v2);getchar();i = LocateVex(G,v1);j = LocateVex(G,v2);/確定頂點(diǎn)v1，v2在圖G中的位置G.arcsij.adj = 1;G.arcsji = G.arcsij;return 1;int FirstAdjVex(MGraph G,int v) /for (int i = 0 ; i G.vexnum; i +) if (G.arcsvi.adj = 1)return i;return -1;int NextAdjVex(MGraph G,int v,int w) /for (int i = w + 1 ; i = 0; w = NextAdjVex(G,v,w) if (!visitedw)DFS(G,w);/對(duì)v的尚未訪問(wèn)的鄰接頂點(diǎn)w遞歸調(diào)用DFSvoid DFSTraverse(MGraph G,char firstVex) /對(duì)圖G作深度優(yōu)先遍歷int v = LocateVex(G,firstVex);DFS(G,v);void BFSTraverse(MGraph G,char firstVex) /對(duì)圖G作廣度優(yōu)先遍歷int v = LocateVex(G,firstVex);char u;int w;Queue Q;for (int i = 0; i = 0; w = NextAdjVex(G,p,w)if (!visitedw) visitedw = true;VisitFunc(G,w);EnQueue(Q,G.vexsw); void main() MGraph G;int i,j;char firstVex;printf(ttt開(kāi)始創(chuàng)建圖n);if (CreateUNG(G)printf(恭喜你，創(chuàng)建圖成功!n);printf(ttt開(kāi)始進(jìn)行深度優(yōu)先遍歷n);printf(設(shè)置遍歷開(kāi)始的頂點(diǎn)n);scanf(%c,&firstVex);getchar();printf(進(jìn)行深度優(yōu)先遍歷序列: );DFSTraverse(G,firstVex);printf(n);printf(ttt開(kāi)始進(jìn)行廣度優(yōu)先遍歷n);printf(設(shè)置遍歷開(kāi)始的頂點(diǎn)n);scanf(%c,&firstVex);prin