图的应用——深度优先遍历和广度优先遍历.doc

华北水利水电大学 数据结构 实验报告20132014学年 第 二 学期 2013级 计算机科学与技术（专升本） 专业班级： 学号： 姓名： 实验四 图的应用一、 实验题目：图的应用深度优先广度优先搜索遍历二、 实验内容：很多涉及图上操作的算法都是以图的遍历操作为基础的。试编写一个算法，实现图的深度优先和广度优先搜索遍历操作。要求：以邻接矩阵或邻接表为存储结构，以用户指定的顶点为起始点，实现连通无向图的深度优先及广度优先搜索遍历，并输出遍历的结点序列。（注：学号为奇数的同学使用邻接矩阵存储结构实现，学号为偶数的同学使用邻接矩阵实现）提示：首先，根据用户输入的顶点总数和边数，构造无向图，然后以用户输入的顶点为起始点，进行深度优先、广度优先搜索遍历，并输出遍历的结果。三、程序源代码：#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(输入图的顶点个数和弧的个数(用空格作为间隔):);scanf(%d %d,&G.vexnum,&G.arcnum);/输入图的顶点个数和弧的个数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(输入弧关联的顶点（两个顶点之间用空格作为间隔）n);for (k = 0; k G.arcnum; k +) printf(输入第%d条弧关联的顶点:,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递归调用DFSvoid DFSTraverse(MGraph G,char firstVex) /对图G作深度优先遍历int v = LocateVex(G,firstVex);DFS(G,v);void BFSTraverse(MGraph G,char firstVex) /对图G作广度优先遍历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开始创建图n);if (CreateUNG(G)printf(恭喜你，创建图成功!n);printf(ttt开始进行深度优先遍历n);printf(设置遍历开始的顶点n);scanf(%c,&firstVex);getchar();printf(进行深度优先遍历序列: );DFSTraverse(G,firstVex);printf(n);printf(ttt开始进行广度优先遍历n);printf(设置遍历开始的顶点n);scanf(%c,&firstVex);prin