数据结构课程设计-- 图的遍历和生成树求解

《数据结构课程设计-- 图的遍历和生成树求解》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、图的遍历和生成树求解摘要：图是一种比线形表和树更为复杂的数据结构。在图形结构中，节点之间的关系可以是任意的，图中任意两个数据元素之间都可能相关。本程序是采用邻接矩阵、邻接表结构存储来实现对图的存储。采用邻接矩阵即为数组表示法，邻接表是图的一种链式存储结构。对图的遍历分别采用了广度优先遍历和深度优先遍历。图的最小生成树基于图的两种存储结构，采用Prim算法和Kruskal算法对图的最小生成树进行求解。关键词：图；存储结构；遍历；最小生成树目录1.设计背景………………………………………………………11.1课程设计目的………………………………………………11.2题目要求………

2、……………………………………………12.设计方案………………………………………………………12.1设计方法……………………………………………………12.2方法实现……………………………………………………23.方案实施………………………………………………………33.1采用的数据结构说明及类型的定义………………………33.2函数功能描述及相关函数的实现…………………………53.3程序中需说明的地方，如用到的宏及代表的意义………164.结果与结论…………………………………………………174.1测试数据及测试结果………………………………………174.2实验结论………………………

3、……………………………195.收获与致谢…………………………………………………196.参考文献……………………………………………………20图的遍历和生成树求解1.设计背景1.1课程设计目的通过本课程设计，加深对《面向对象程序设计C++》课程所学知识的理解，熟练掌握和巩固C++语言的基本知识和语法规范,掌握使用面向对象程序设计语言C++，或面向对象开发平台VisualC++等,培养调查研究、查阅技术文献、资料、手册以及编写技术文献的能力。学会编制结构清晰、风格良好的C++语言程序，从而具备利用计算机编程分析解决综合性实际问题的初步能力。1.2题目要求课程设计是培养学生综合

4、运用所学知识,发现,提出,分析和解决实际问题,锻炼实践能力的重要环节,是对学生实际工作能力的具体训练和考察过程.通过课程设计，巩固和加深对队列以及图等理论知识的理解；掌握现实复杂问题的分析建模和解决方法，掌握包括问题描述、系统分析、设计建模、代码实现、结果分析等的方法；提高利用计算机分析解决综合性实际问题的基本能力；锻炼个人动手能力，历练自身素质。2.设计方案2.1设计方法2.1.1问题的分析和结构的设计思路1）图的遍历和生成树求解所有功能：图的生成、图的遍历、最小生成树求解。2）需要创建所有图的存储结构(邻接矩阵存储结构和邻接表存储结构)。3）程序设计的目的是通过屏幕

5、上输出的提示语句，进行相应的操作。4）选择适当的算法，实现图的遍历和最小生成树的求解等功能。5）选择适当的变量，来表示图相应的顶点、边、边的权值等信息。6）当输入的信息出错时，程序应给错误信息提示，使程序设计得全面周密。2.1.2图的遍历和生成树求解的算法思想及设计1）由于图的存储结构不同，故采用邻接矩阵和邻接表两种存储结构建立图。2）对图的深度遍历基于邻接矩阵，广度遍历基于邻接表。-20-图的遍历和生成树求解3）基于邻接矩阵存储结构，用prim算法求图的最小生成树。4）基于邻接表存储结构，用Kruskal算法求图的最小生成树。5）综合1、2、3三点因素，可以采用队列来

6、实现对图的广度优先遍历的算法，其示意图如下：Q.frontnext其中：1.Q.front为队头指针,Q.rear为队尾指针2.data域存图的边权值和顶点位序等相关信息。3.next域指向与改结点同类型的下一个结点nextdatadatanextQ.rear6）图遍历和生成树求解的总体结构框图如下：图的遍历和生成树的求解建立邻接矩阵输出邻接矩阵BFS遍历建立邻接表输出邻接表DFS遍历Prim求最小生成树Kruskal求最小生成树2.2方法实现2.2.1创建结点-20-图的遍历和生成树求解1）建立队列LinkQueue，以及队头指针front、队尾指针rear。2)建立

7、图的存储类型MGraph,以及顶点向量vexs[]。3)建立图的邻接矩阵AdjMatrix[][]，以及边的权值。4)建立图的邻接表ALGraph,以及邻接表头结点的类型AdjList[]，弧的结点结构类型ArcNode。2.2.2编写函数建立具体的功能实现函数，如初始化、录入、输出等。1.基于邻接矩阵创建图CreateUDN(MGraph&G,AdjMatrix&GA)2.基于邻接表建立图CreateALGraph(ALGraph&G)3.邻接矩阵的输出Display(MGraphG,AdjMatrixGA)4.邻接表的输出Displa