图的遍历和生成树求解实现

目录摘要...............................................................2序言...............................................................3正文...............................................................41.问题描述.....................................................41.1.图的遍历和生成树求解实现................................41.2基本功能................................................41.3输入输出................................................42.逻辑设计....................................................52.1设计思路................................................52.2数据结构设计...........................................52.3软件设计...............................................63.详细设计....................................................73.1定义程序中的数据及其数据结构.............................73.2主函数和其他函数的伪码算法.............................83.3主要函数的程序流程图..................................164.调试分析...................................................194.1实际完成的情况说明.....................................194.2程序的性能分析，时空分析...............................194.3上机过程中出现的问题及其解决方案.......................194.4程序中可以改进的地方说明...............................195.测试结果...................................................205.1主界面.................................................205.2程序运行截图...........................................215.3创建一个有权连通图.....................................226.使用说明书..................................................23设计总结..........................................................24参考文献..........................................................25致谢..............................................................26附录..............................................................27摘要很多涉及图上操作的算法都是以图的遍历操作为基础的，该设计要求写一个程序，演示出图遍历的过程，并给出图的生成树（网的最小代价生成树）。通过该题目的设计过程，可以加深理解图数据结构及队列的逻辑结构、存储结构及图的深度优先和广度优先遍历过程，掌握图数据据结构上基本运算的实现，进一步理解和熟练掌握课本中所学的各种数据结构，学会如何把学到的知识用于解决实际问题，培养动手能力。关键字：图、深度优先遍历、广度优先遍历、生成树。序言计算机科学与技术本科专业《算法与数据结构课程设计》是在《算法与数据结构》课程结束之后，要求学生能够设计程序，进一步理解和熟练掌握课本中所学的各种数据结构，学会如何把学到的知识用于解决实际问题，培养自己的动手能力，独立思考能力，发现问题并解决问题能力而开设的课程。从课程性质上讲，《算法与数据结构课程设计》是一门技术实践课。其要求是：学会分析研究计算机加工的数据结构的特点，以便为应用涉及的数据选择适当的逻辑结构，存储结构及其相应的算法，并初步掌握算法的时间分析和空间分析的技术。另一方面，在前期学习过程中对复杂程序设计理解掌握基础上做进一步的实践训练，并且能编写出结构清楚，正确易读，符合软件工程规范的程序。很多涉及图上操作的算法都是以图的遍历操作为基础的，该设计要求写一个程序，演示出图遍历的过程，并给出图的生成树（网的最小代价生成树）。通过该题目的设计过程，可以加深理解图数据结构及队列的逻辑结构、存储结构及图的深度优先和广度优先遍历过程，掌握图数据据结构上基本运算的实现，进一步理解和熟练掌握课本中所学的各种数据结构，学会如何把学到的知识用于解决实际问题，培养学生的动手能力。由于此题目需要较多的数据输入，同时功能模块也比较的多，故在命令提示符下采用了图形化菜单式的界面，使得选择功能和输入数据都比较容易。正文1.问题描述1.1.图的遍历和生成树求解实现图是一种较线性表和树更为复杂的数据结构。在线性表中，数据元素之间仅有线性关系，每个数据元素只有一个直接前驱和一个直接后继；在树形结构中，数据元素之间有着明显的层次关系，并且每一层上的数据元素可能和下一层中多个元素（及其孩子结点）相关但只能和上一层中一个元素（即双亲结点）相关；而在图形结构中，节点之间的关系可以是任意的，图中任意两个数据元素之间都可能相关。生成树求解主要利用普利姆和克雷斯特算法求解最小生成树，只有强连通图才有生成树。1.2基本功能1)先任意创建一个图；2)图的DFS,BFS的递归和非递归算法的实现3)最小生成树（两个算法）的实现，求连通分量的实现4)要求用邻接矩阵、邻接表等多种结构存储实现1.3输入输出输入数据类型为整型和字符型，输出为整型和字符2.逻辑设计2.1设计思路1)图的邻接矩阵存储：根据所建无向图的结点数n,建立n*n的矩阵，其中元素全是无穷大（int_max），再将边的信息存到数组中。其中无权图的边用1表示，无边用0表示；有全图的边为权值表示，无边用∞表示。2)图的邻接表存储：将信息通过邻接矩阵转换到邻接表中，即将邻接矩阵的每一行都转成链表的形式将有边的结点进行存储。3)图的广度优先遍历：假设从图中的某个顶点v出发，在访问了v之后依次访问v的各个未曾访问过的邻接点，然后再访问此邻接点的未被访问的邻接点，并使“先被访问的顶点的邻接点”先于“后被访问的顶点的邻接点”被访问，直至图中所有已被访问的顶点的邻接点都被访问到。若此时图中还有未被访问的，则另选未被访问的重复以上步骤，是一个非递归过程。4)图的深度优先遍历：假设从图中某顶点v出发，依依次访问v的邻接顶点，然后再继续访问这个邻接点的系一个邻接点，如此重复，直至所有的点都被访问，这是个递归的过程。5)图的连通分量：这是对一个非强连通图的遍历，从多个结点出发进行搜索，而每一次从一个新的起始点出发进行搜索过程中得到的顶点访问序列恰为其连通分量的顶点集。本程序利用的图的深度优先遍历算法。2.2数据结构设计ADTQueue{数据对象：D={ai|ai∈ElemSet,i=1,2,3……，n,n≥0}数据关系：R1={ai-1,ai|ai-1,ai∈D,i=1,2,3,……，n}基本操作：InitQueue(&Q)操作结果：构造一个空队列Q。QueueEmpty(Q)初始条件：Q为非空队列。操作结果：若Q为空队列，则返回真，否则为假。EnQueue(&Q,e)初始条件：Q为非空队列。操作结果：插入元素e为Q的新的队尾元素。DeQueue(&Q,e)初始条件：Q为非空队列。操作结果：删除Q的队头元素，并用e返回其值。}ADTQueueADTGraph{数据对象V：V是具有相同特性的数据元素的集合，称为顶点集。数据关系R：R={VR}VR={v,w|v,w∈V且P（v，w）,v,w表示从v到w的弧，谓词P（v,w）定义了弧v,w的意义或信息}基本操作P：CreatGraph(&G,V,VR);初始条件：V是图的顶点集，VR是图中弧的集合。操作结果：按V和VR的定义构造图G。BFSTraverse(G,visit());初始条件：图G存在，Visit是定点的应用函数。操作结果：对图进行广度优先遍历。在遍历过程中对每个顶点调用函数Visit一次且仅一次。一旦visit（）失败，则操作失败。DFSTraverse(G,visit());初始条件：图G存在，Visit是定点的应用函数。操作结果：对图进行广度优先遍历。在遍历过程中对每个顶点调用函数Visit一次且仅一次。一旦visit（）失败，则操作失败。DFStra_fen(G)初始条件：图G存在，存在图的深度优先遍历算法。操作结果：从多个顶点对图进行深度优先遍历，得到连通分量。}ADTGraph;2.3软件设计maincreatMGraph_L(G)creatadj(gra,G)ljjzprint(G)adjprint(gra,G)BFSTraverse(gra)DFStra(gra)DFSTraverse_fen(gra)MiniSpanTree_PRIM(g,G.vexnum)MiniSpanTREE_KRUSCAL(G,gra)01234567函数名返回值类型creatMGraph_L(G)intcreatadj(gra,G)intljjzprint(G)voidadjprint(gra,G)voidBFSTraverse(gra)voidDFStra(gra)int3.详细设计3.1定义程序中的数据及其数据结构1）邻接矩阵定义:typedefstructArcCell{VRTypeadj;//VRType是顶点关系类型。对无权图，用1或0表示相邻否；对带权图，则为权值类型InfoType*info;//该弧相关信息的指针}ArcCell,AdjMatrix[max][max];typedefstruct{VertexTypevexs[max];//顶点向量AdjMatrixarcs;//邻接矩阵intvexnum,arcnum;//图的当前顶点数和弧数}MGraph_L;2）邻接表的定义:typedefstructArcNode//弧结点{intadjvex;//该弧指向的顶点的位置structArcNode*nextarc;//指向下一条弧的指针InfoType*info;//该弧相关信息的指针}ArcNode;DFSTraverse_fen(gra)intMiniSpanTree_PRIM(g,G.vexnum)intMiniSpanTREE_KRUSCAL(G,gra)voidtypedefstructVNode//邻接链表顶点头接点{VertexTypedata;//顶点信息ArcNode*firstarc;//指向第一条依附该顶点的弧的指针}VNode,AdjList;typedefstruct//图的定义{AdjListvertices[max];intvexnum,arcnum;//图的当前顶点数和弧数}ALGraph;3）队列定义:typedefstructQNode{QElemTypedata;struc