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

《图的遍历和生成树求解实现》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、目录摘要2序言3正文41.问题描述41.1.图的遍历和生成树求解实现41.2基本功能41.3输入输出42.逻辑设计42.1设计思路42.2数据结构设计52.3软件设计63.详细设计73.1定义程序中的数据及其数据结构73.2主函数和其他函数的伪码算法83.3主要函数的程序流程图154.调试分析184.1实际完成的情况说明184.2程序的性能分析，时空分析184.3上机过程中出现的问题及其解决方案184.4程序中可以改进的地方说明185.测试结果195.1主界面195.2程序运行截图205.3创建一个有权连通图216.使用说明书

2、22设计总结23参考文献24致谢25附录26摘要很多涉及图上操作的算法都是以图的遍历操作为基础的，该设计要求写一个程序，演示出图遍历的过程，并给出图的生成树（网的最小代价生成树）。通过该题目的设计过程，可以加深理解图数据结构及队列的逻辑结构、存储结构及图的深度优先和广度优先遍历过程，掌握图数据据结构上基本运算的实现，进一步理解和熟练掌握课本中所学的各种数据结构，学会如何把学到的知识用于解决实际问题，培养动手能力。关键字：图、深度优先遍历、广度优先遍历、生成树。序言计算机科学与技术本科专业《算法与数据结构课程设计》是在《算法与数

3、据结构》课程结束之后，要求学生能够设计程序，进一步理解和熟练掌握课本中所学的各种数据结构，学会如何把学到的知识用于解决实际问题，培养自己的动手能力，独立思考能力，发现问题并解决问题能力而开设的课程。从课程性质上讲，《算法与数据结构课程设计》是一门技术实践课。其要求是：学会分析研究计算机加工的数据结构的特点，以便为应用涉及的数据选择适当的逻辑结构，存储结构及其相应的算法，并初步掌握算法的时间分析和空间分析的技术。另一方面，在前期学习过程中对复杂程序设计理解掌握基础上做进一步的实践训练，并且能编写出结构清楚，正确易读，符合软件工程

4、规范的程序。很多涉及图上操作的算法都是以图的遍历操作为基础的，该设计要求写一个程序，演示出图遍历的过程，并给出图的生成树（网的最小代价生成树）。通过该题目的设计过程，可以加深理解图数据结构及队列的逻辑结构、存储结构及图的深度优先和广度优先遍历过程，掌握图数据据结构上基本运算的实现，进一步理解和熟练掌握课本中所学的各种数据结构，学会如何把学到的知识用于解决实际问题，培养学生的动手能力。由于此题目需要较多的数据输入，同时功能模块也比较的多，故在命令提示符下采用了图形化菜单式的界面，使得选择功能和输入数据都比较容易。正文1.问题描述

5、1.1.图的遍历和生成树求解实现图是一种较线性表和树更为复杂的数据结构。在线性表中，数据元素之间仅有线性关系，每个数据元素只有一个直接前驱和一个直接后继；在树形结构中，数据元素之间有着明显的层次关系，并且每一层上的数据元素可能和下一层中多个元素（及其孩子结点）相关但只能和上一层中一个元素（即双亲结点）相关；而在图形结构中，节点之间的关系可以是任意的，图中任意两个数据元素之间都可能相关。生成树求解主要利用普利姆和克雷斯特算法求解最小生成树，只有强连通图才有生成树。1.2基本功能1)先任意创建一个图；2)图的DFS,BFS的递归和

6、非递归算法的实现3)最小生成树（两个算法）的实现，求连通分量的实现4)要求用邻接矩阵、邻接表等多种结构存储实现1.3输入输出输入数据类型为整型和字符型，输出为整型和字符2.逻辑设计2.1设计思路1)图的邻接矩阵存储：根据所建无向图的结点数n,建立n*n的矩阵，其中元素全是无穷大（int_max），再将边的信息存到数组中。其中无权图的边用1表示，无边用0表示；有全图的边为权值表示，无边用∞表示。2)图的邻接表存储：将信息通过邻接矩阵转换到邻接表中，即将邻接矩阵的每一行都转成链表的形式将有边的结点进行存储。3)图的广度优先遍历：假

7、设从图中的某个顶点v出发，在访问了v之后依次访问v的各个未曾访问过的邻接点，然后再访问此邻接点的未被访问的邻接点，并使“先被访问的顶点的邻接点”先于“后被访问的顶点的邻接点”被访问，直至图中所有已被访问的顶点的邻接点都被访问到。若此时图中还有未被访问的，则另选未被访问的重复以上步骤，是一个非递归过程。4)图的深度优先遍历：假设从图中某顶点v出发，依依次访问v的邻接顶点，然后再继续访问这个邻接点的系一个邻接点，如此重复，直至所有的点都被访问，这是个递归的过程。5)图的连通分量：这是对一个非强连通图的遍历，从多个结点出发进行搜索，

8、而每一次从一个新的起始点出发进行搜索过程中得到的顶点访问序列恰为其连通分量的顶点集。本程序利用的图的深度优先遍历算法。2.2数据结构设计ADTQueue{数据对象：D={ai

9、ai∈ElemSet,i=1,2,3……，n,n≥0}数据关系：R1={

10、ai-1