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

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