C++面向对象程序设计课设报告无向图的深度与广度的遍历

1、目 录 一、题目概述（内容及要求）4二、功能分析5三、设计6四、运行与测试9五、总结11参考文献12附录.12一、题目概述（内容及要求）1.深度优先搜索 深度优先搜索遍历类似于树的先根遍历，是树的先根遍历的推广。 假设初始状态是图中所有顶点未曾被访问，则深度优先搜索可从图中某个顶点v0出发，访问此顶点，然后依次从v的未访问的邻接点出发深度优先遍历，直至图中所有和v有路径相通的顶点都被访问到；若此时图中尚有顶点未被访问，则另选图中一个未被访问的顶点，重复上述过程，直至所有的顶点都被访问。2.广度优先搜索 广度优先搜索遍历类似于树的按层次遍历的过程。 假设从图中某顶点v出发，在访问了v之后依次访问

2、v的各个未曾访问过的邻接点，然后分别从这些邻接点出发依次访问它们的邻接点，并使“先被访问的顶点的邻接点”被访问，直至图中所有已被访问的顶点的邻接点都被访问到。若此时图中尚有顶点未被访问，则另选图中一个未被访问的顶点，重复上述过程，直至所有的顶点都被访问 实现无向连通图的深度与广度遍历。要求：1.设计数据结构，存储结构； 2.在c兼容环境完成上述题目的代码编写与调试； 3.程序运行界面交互性好； 4.软件运行，给出测试数据。二、功能分析1.深度优先搜索： 如图2.1所示，假设从顶点v1出发，进行搜索，在访问了顶点v1之后，选择邻接点v2，。因为v2未曾访问，则从v2出发进行搜索。以次类推，接着从

3、v4，v8，v5出发进行搜索。在访问了v5之后，由于v5的邻接点都已被访问，则搜索回到v8.由于同样的理由，搜索继续回到v4，v2，直到v1，此时由于v1的另一个结点未被访问，则搜索又从v1到v3，再继续进行下去。由此，得到的顶点访问顺序为：v1->v2->v4->v8->v5->v3->v6->v7算法： void DFS(Graph G,int v)/从第v个顶点出发递归深度优先遍历图。visitedv=TRUE;VisitFunc(v); /访问第v个顶点for(w=FirstAdjVex(G,v);w>=0;w=NextAdjVex(G,

4、v,w) if(!visitedw) DFS(G,w);/对v的尚未访问的邻接顶点w递归调用DFSV4V5V8V6V2V3V1V7图2.1 2.广度优先搜索： 如图2.1所示，假设从顶点v1出发，进行搜索,首先访问顶点v1和v1的邻接点v2和v3，然后依次访问v2的邻接点v4和v5及v3的邻接点v6和v7，最后访问v4的邻接点v8. 由于这些顶点的邻接点均已被访问，并且图中所有顶点都已被访问，由此，完成了图的遍历。得到的顶点访问序列为v1->v2->v3->v4->v5->v6->v7->v8算法：void BFSTraverse(Graph G,St

5、atus(*Visit)(int v) /按广度优先非递归遍历图G，使用辅助队列Q和访问标志数组visited。 for(v=0;v<G.vexnum;+v) visitedv=FALSE;InitQueue(Q); /置空的辅助队列Qfor(v=0;v<G.vexnum;+v) if(!visitedv) /v尚未访问 visitedv=TRUE;visitv; EnQueue(Q,v); /v入队列 while(!QueueEmpty(Q) DeQueue(Q,u); /队头元素出列并置为u for(w=FirstAdjVex(G,u);w>=0;w=NextAdjVex

6、(G,u,w) if(!Visitedw) /w为u的尚未访问的邻接顶点 Visitedw=TRUE; Visit(w); EnQueue(Q,w); 三、设计3.1 总体设计 采用邻接矩阵作为图的存储结构。程序中主要用到以下抽象数据类型： 抽象数据类型的定义 typedef struct char *vexs; /顶点向量 int arcsMAX_VEXMAX_VEX; /邻接矩阵 int vexnum,arcnum; /图的当前顶点数和弧数 Graph; 基本操作 CreateUDN(Graph &G) 操作结果：用邻接矩阵创建带权无向网图。 DFS(Graph G,int k)

7、操作结果：对已存在的图进行深度优先遍历。 BFS(Graph G) 操作结果：对已存在的图进行广度优先遍历。 choose(Graph G) 操作结果：对将要实现的操作步骤进行选择。 3.2功能模块图主菜单构造图主菜单深度优先搜索广度优先搜索图3.1功能模块图3.2函数设计 程序设计中主要包括下列函数 用邻接矩阵创建一个图： void CreateUDN(Graph &G) 用邻接矩阵创建一个带权无向网图; 输入顶点数和弧数; 输入各个顶点及各条弧; 递归方法实现图的遍历： void DFS(Graph G, int k) 用递归的方法访问图中的结点; 对图进行深度优先遍历; 非递归方

8、法实现图的遍历： void BFS(Graph G) 用队列辅助访问图中的结点; 对图进行广度优先遍历; 选择输出需要的遍历方法： void choose(Graph G) 给出程序运行的选项; 对相应的输入选项调用相应的函数以执行操作;3.3 程序框图 开始创建无向图函数数据输入选择模块深度优先遍历广度优先遍历数据输出数据输出选择模块退出程序结束图3.2流程图四、运行与测试4.1运行结果 4.1.1测试数据abced图4.1程序测试用例图顶点的关系如图4.1所示，输入：顶点数 5，弧数 5；顶点 a b c d e；顶点之间的关系：a c 1b d 1c e 1d a 1e b 1选择1，进

9、行广度优先遍历。选择2，进行深度优先遍历。选择3，结束。4.1.2理想测试结果广度优先遍历：a->c->d->e->b深度优先遍历：a->c->e->b->d4.1.3实际运行结果 图4.2运行结果与预期一致。五、总结通过这次课程设计，我受益颇多： 首先，上课时听的理论知识，似乎很容易接受，以及各种算法都能够比较轻松的理解，但是在真正的运用过程中，并不能把理论知道很好的和实践结合起来。感觉自己有点眼高手低，有些知识点的应用只有在实践中才能慢慢体会，在平时做实验时，总感到有些无从下手。因此，在学知识的过程中，一定要多动手、动脑，将所学的知识熟练掌握

10、，自如运用。 其次，通过这次课程设计，对我的逻辑思维能力是一个很大的锻炼，再有，它还加强了我的系统思考问题的能力，在编程方面，我开始从整体的角度来考虑问题了，而不再像以前一样的，胡乱动手。也就是因为先前的这种编程习惯，使得我在课程设计过程中浪费了不少的时间，尝到了教训。 通过这次课程设计，我学习了很多平时很少关注的知识点，比如循环链，递归的应用，也增强了自己的实践能力和编写程序的能力。 图是一种较为复杂且重要的数据结构，其特殊性在于图形结构中结点之间的关系可以是任意的，图中任意两个数据元素之间都有可能相关。用邻接矩阵作为图的数据存储结构很好地解决了图的结构难点， 借助于邻接矩阵容易判定任意两个

11、顶点之间是否有边(或弧)相连，并容易求得各个顶点的度。该程序通俗易懂且实用性强，并且该程序清单详细具体、全面、具有很强的可读性；系统整体上比较完美，可以从键盘获取输入元素，并且可以根据用户输入进行选择性地输出；整体输出画面效果整洁、大方。参考文献1. 严蔚敏，吴伟民编著. 数据结构（C语言版） 北京：清华大学出版社，20072.c语言程序设计.马秀丽，李筠，刘志妩编著.北京:清华大学出版社，2008.3附录程序代码#include <stdio.h>#include <stdlib.h>#include <iostream>using namespace s

12、td; #define INFINITY 32767 #define MAX_VEX 20 /最大顶点个数 #define QUEUE_SIZE (MAX_VEX+1) /队列长度 bool *visited; /访问标志数组 int z=1; typedef struct /图的邻接矩阵存储结构 char *vexs; /顶点向量 int arcsMAX_VEXMAX_VEX; /邻接矩阵 int vexnum,arcnum; /图的当前顶点数和弧数 Graph; class Queue /队列类 public: void InitQueue() base=(int *)malloc(QUE

13、UE_SIZE*sizeof(int); front=rear=0; void EnQueue(int e) baserear=e; rear=(rear+1)%QUEUE_SIZE; void DeQueue(int &e) e=basefront; front=(front+1)%QUEUE_SIZE; int *base; int front;int rear; ; int Locate(Graph G,char c) /图G中查找元素c的位置for(int i=0;i<G.vexnum;i+)if(G.vexsi=c)return i;return -1; void Cr

14、eateUDN(Graph &G) /创建无向网int i,j,w,s1,s2;char a,b,c,temp; printf("输入顶点数和弧数:"); scanf("%d%d",&G.vexnum,&G.arcnum); temp=getchar(); /接收回车G.vexs=(char *)malloc(G.vexnum*sizeof(char); /分配顶点数目 printf("输入%d个顶点.n",G.vexnum);for(i=0;i<G.vexnum;i+) /初始化顶点scanf(&quo

15、t;%c",&G.vexsi); temp=getchar(); /接收回车 for(i=0;i<G.vexnum;i+) /初始化邻接矩阵for(j=0;j<G.vexnum;j+) G.arcsij=INFINITY; printf("输入%d条弧.n",G.arcnum);for(i=0;i<G.arcnum;i+) /初始化弧printf("输入弧%d: ",i); scanf("%c %c %d%c",&a,&b,&w,&c); /输入一条边依附的顶点和权值

16、s1=Locate(G,a); s2=Locate(G,b); G.arcss1s2=G.arcss2s1=w; int FirstVex(Graph G,int k) /图G中顶点k的第一个邻接顶点if(k>=0 && k<G.vexnum) /k合理 for(int i=0;i<G.vexnum;i+) if(G.arcski!=INFINITY) return i; return -1; /图G中顶点i的第j个邻接顶点的下一个邻接顶点 int NextVex(Graph G,int i,int j) if(i>=0 && i<

17、G.vexnum && j>=0 && j<G.vexnum) /i,j合理 for(int k=j+1;k<G.vexnum;k+)if(G.arcsik!=INFINITY) return k; return -1; /深度优先遍历 void DFS(Graph G,int k) int i; if(k=-1) /第一次执行DFS时,k为-1 for(i=0;i<G.vexnum;i+) if(!visitedi) DFS(G,i); /对尚未访问的顶点调用DFS else visitedk=true;if(z=1) printf(&

18、quot;%c",G.vexsk); else printf(" -> %c",G.vexsk);+z; /访问第k个顶点 if(z-1)%G.vexnum=0)z=1; for(i=FirstVex(G,k);i>=0;i=NextVex(G,k,i) if(!visitedi) DFS(G,i); /对k的尚未访问的邻接顶点i递归调用DFS /广度优先遍历 void BFS(Graph G) int k; Queue Q; /辅助队列Q Q.InitQueue(); for(int i=0;i<G.vexnum;i+) if(!visited

19、i) /i尚未访问visitedi=true; printf("%c ",G.vexsi);Q.EnQueue(i);/i入列 while(Q.front!=Q.rear) Q.DeQueue(k); /队头元素出列并置为k for(int w=FirstVex(G,k);w>=0;w=NextVex(G,k,w)if(!visitedw) /w为k的尚未访问的邻接顶点 visitedw=true; printf("-> %c ",G.vexsw); Q.EnQueue(w); printf("n 请继续选择:n"); void choose(Graph G) /对输入选项调用相应的函数执行操作 int i,m; visited=(bool *)malloc(