1、 图的遍历和生成树求解图的遍历和生成树求解 摘要：摘要：图是一种比线形表和树更为复杂的数据结构。在图形结构中，节点之间 的关系可以是任意的，图中任意两个数据元素之间都可能相关。本程序是采用邻 接矩阵、邻接表结构存储来实现对图的存储。采用邻接矩阵即为数组表示法，邻 接表是图的一种链式存储结构。 对图的遍历分别采用了广度优先遍历和深度优先 遍历。图的最小生成树基于图的两种存储结构，采用 Prim 算法和 Kruskal 算法 对图的最小生成树进行求解。 关键词：关键词：图；存储结构；遍历 ；最小生成树 目目 录录 1.1.设计背景设计背景1 1.1 课程设计目的1 1.2 题目要求1 2.2.设计
2、方案设计方案1 2.1 设计方法1 2.2 方法实现2 3.3. 方案实施方案实施3 3.1 采用的数据结构说明及类型的定义3 3.2 函数功能描述及相关函数的实现5 3.3 程序中需说明的地方，如用到的宏及代表的意义16 4.4. 结果与结论结果与结论 17 4.1 测试数据及测试结果17 4.2 实验结论19 5.5.收获与致谢收获与致谢19 6.6.参考文献参考文献20 图的遍历和生成树求解图的遍历和生成树求解 - 1 - 1.1. 设计背景设计背景 1.11.1 课程设计目的课程设计目的 通过本课程设计，加深对面向对象程序设计 C+课程所学知识的理解， 熟练掌握和巩固 C+语言的基本知
3、识和语法规范,掌握使用面向对象程序设计语 言 C+，或面向对象开发平台 Visual C+等,培养调查研究、查阅技术文献、资 料、手册以及编写技术文献的能力。学会编制结构清晰、风格良好的 C+语言程 序，从而具备利用计算机编程分析解决综合性实际问题的初步能力。 1.1.2 2 题目要求题目要求 课程设计是培养学生综合运用所学知识,发现,提出,分析和解决实际问题, 锻炼实践能力的重要环节,是对学生实际工作能力的具体训练和考察过程. 通过 课程设计，巩固和加深对队列以及图等理论知识的理解；掌握现实复杂问题的分 析建模和解决方法，掌握包括问题描述、系统分析、设计建模、代码实现、结果 分析等的方法；提
4、高利用计算机分析解决综合性实际问题的基本能力；锻炼个人 动手能力，历练自身素质。 2.设计方案 2 2.1.1 设计方法设计方法 2.12.1. .1 1 问题的分析和结构的设计思路问题的分析和结构的设计思路 1） 图的遍历和生成树求解所有功能：图的生成、图的遍历、最小生成树求 解。 2） 需要创建所有图的存储结构(邻接矩阵存储结构和邻接表存储结构)。 3）程序设计的目的是通过屏幕上输出的提示语句，进行相应的操作。 4）选择适当的算法，实现图的遍历和最小生成树的求解等功能。 5）选择适当的变量，来表示图相应的顶点、边、边的权值等信息。 6）当输入的信息出错时，程序应给错误信息提示，使程序设计得
5、全面周密。 2.2.1.1.2 2 图的遍历和生成树求解图的遍历和生成树求解的算法思想及设计的算法思想及设计 1） 由于图的存储结构不同， 故采用邻接矩阵和邻接表两种存储结构建立图。 2）对图的深度遍历基于邻接矩阵，广度遍历基于邻接表。 图的遍历和生成树求解图的遍历和生成树求解 - 2 - 3）基于邻接矩阵存储结构，用 prim 算法求图的最小生成树。 4）基于邻接表存储结构，用 Kruskal 算法求图的最小生成树。 5）综合 1、2、3 三点因素，可以采用队列来实现对图的广度优先遍历的算 法，其示意图如下： 6）图遍历和生成树求解的总体结构框图如下： 2 2. .2 2 方法实现方法实现 2.22.2. .1 1 创建结点创建结点 next data Q.front next data next Q.rear 其中： 1. Q.front 为队头指针,Q.rear 为队尾指针 2. data 域存图的边权值和顶点位序等相关信息。 3. next 域指向与改结点同类型的下一个结点 图 的 遍 历 和 生 成 树 的 求 解 建立邻接矩阵 输出邻接矩阵 BFS 遍历 建立邻接表 输出邻接表 DFS 遍历 Prim 求最小生成
