数据结构实验五---图的遍历及其应用实现

《数据结构实验五---图的遍历及其应用实现》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、实验五图的遍历及其应用实现实验目的1.2.3.熟悉图常用的存储结构。掌握在图的邻接矩阵和邻接表两种结构上实现图的两种遍历方法实现。会用图的遍历解决简单的实际问题。二实验内容［题目］:从键盘上输入图的顶点和边的信息，建立图的邻接表存储结构，然后以深度优先搜索和广度优先搜索遍历该图，并输出起对应的遍历序列.试设计程序实现上述图的类型定义和基本操作，完成上述功能。该程序包括图类型以及每一种操作的具体的函数定义和主函数。三、实验步骤(-).数据结构与核心算法的设计描述：本实验主要在于图的基本操作，关键是图的两种遍历，仔细分析图的遍历的特点，不难发现

2、，其符合递归的特点，因此可以采用递归的方法遍历。本实验图的存储结构主要采用邻接表，总共分为四个模块：图的创建、位置的查找、深度优先遍历、广度优先遍历。以下是头文件中数据结构的设计和相关函数的声明：#include#include#include#defineOVERFLOW-2ttdefineMAX_VERTEX_NUM50SdefineMAXQSIZE100#defineOKtypedeftypedeftypedeftypedeftypedef//最大顶点数#ncludc

3、alloc.h>1intintintVRType;InfoType;QElemType;cnum{DG,DN,UDG,UDN}GraphKind;intadjvex;structArcNodeTnfoType*info;}ArcNode;typedefstruetstructArcNode//弧结点//邻接点域，存放与Vi邻接的点在表头数组中的位置*nextarc;//链域指向vi的下一条边或弧的结点，VNodc//定义与弧相关的权值，无权则为0〃表头结点//存放顶点信息//指示第一个邻接点charvexdata;structArcNode

4、*fitstarc;}VNode,AdjList[MAX_VERTEX_NUM];typedefstruet{//图的结构定义AdjListvertices;//顶点向量intvexnum,arcnum;//vexnum为顶点数arcnum为弧或边的个数GraphKindkind;//图的种类标志}MGraph;typedefstructQueue//构建循环队列{QElemType*base;intfront;intrear;(Queue;voidCreateGraph(MGraph&G);voidDFSTraverse(MGraph&G

5、);voidBFSTraverse(MGraph&G);〃图的创建//深度优先遍历//广度优先遍历intLocatcVcx(MGraph&G,char&v);//查找顶点v的位置(二)、函数调用及主函数设计voidmain(){intx;MGraphG;CreatcGraph(G);cout<>x;if(x二二1){DFSTraverse(G);cout«〃深度优先搜索结束!〃〈〈cndl;}elseif(x==2){B

6、FSTraverse(G);cout«/zr度优先搜索结束!/z«endl;}elsecout«，z输入有误!zz«cndl«/z再见!z/«cndl;}(三)、实验总结由于图的基木操作在图这一章节中起着很主要的作用，所以在实验前就对实验做了充分的准备，实验的成功核心在于两种遍历的实现，因此只有充分理解遍历算法的精髓，才能更好的做好实验。尽管实验过程中不同模块遇到了不同程度的困难，但是经过详细的设计和反复的测试、调试，实验最终结果达到了实验的预期结果。主要算法流程图及程序清单1、主要算法流程图:DFS(BFS同DFS类似，故不再列举)2、程

7、序清单♦图的创建模块：voidCrcatcGraph(MGraph&G){//生成图G的存储结构-邻接表inti=0,j=O,k;cout«/z请输入顶点的数目、边的数目〃cin»G.vexnum»G.arcnum»m;//输入顶点数、边数和图类cout«/ztt请依次输入各个顶点的数值:〃；for(i=0;i>G.verticcs[i].vcxdata;G.verticcsEi]・firstarc二NULL;}charsv,tv;cout«/ztt请依次输入各边的始点和终点<〈endl;f

8、or(k=0;k>sv;cout«，z请输入第条边的终点：〃；