精品文档---下载后可任意编辑##大学数据结构课程设计报告题目： 图的遍历和生成树求解 院（系）： 计算机工程学院 学生姓名:班级：学号:起迄日期: 2024.6.20 指导老师: 2024—2024 年度 第 2 学期一、需求分析1.问题描述：图的遍历和生成树求解实现图是一种较线性表和树更为复杂的数据结构。在线性表中，数据元素之间仅有线性关系，每个数据元素只有一个直接前驱和一个直接后继；在树形结构中，数据元素之间有着明显的层次关系，并且每一层上的数据元素可能和下一层中多个元素（及其孩子结点）相关但只能和上一层中一个元素（即双亲结点）相关；而在图形结构中，节点之间的关系可以是任意的，图中任意两个数据元素之间都可能相关。生成树求解主要利用普利姆和克雷斯特算法求解最小生成树，只有强连通图才有生成树。1) 先任意创建一个图；2) 图的 DFS,BFS 的递归和非递归算法的实现3) 最小生成树（两个算法）的实现，求连通重量的实现4) 要求用邻接矩阵、邻接表等多种结构存储实现 输入数据类型为整型和字符型，输出为整型和字符二、 概要设计1.设计思路：a.图的邻接矩阵存储：根据所建无向图的结点数 n,建立 n*n 的矩阵，其中元素全是无穷大（int_max），再将边的信息存到数组中。其中无权图的边用 1 表示，无边用 0 表示；有全图的边为权值表示，无边用∞表示。b.图的邻接表存储：将信息通过邻接矩阵转换到邻接表中，即将邻接矩阵的每一行都转成链表的形式将有边的结点进行存储。c.图的广度优先遍历：假设从图中的某个顶点 v 出发，在访问了 v 之后依次访问 v 的各个未曾访问过的邻接点，然后再访问此邻接点的未被访问的邻接点，并使“先被访问的顶点的邻接点”先于“后被访问的顶点的邻接点”被访问，直至图中所有已被访问的顶点的邻接点都被访问到。若此时图中还有未被访问的，则另选未被访问的重复以上步骤，是一个非递归过程。d.图的深度优先遍历：假设从图中某顶点 v 出发，依依次访问 v 的邻接顶点，然后再继续访问这个邻接点的系一个邻接点，如此重复，直至所有的点都被访问，这是个递归的过程。e.图的连通重量：这是对一个非强连通图的遍历，从多个结点出发进行搜索，而每一次从一个新的起始点出发进行搜索过程中得到的顶点访问序列恰为其连通重量的顶点集。本程序利用的图的深度优先遍历算法。 2.数据结构设计：ADT Queue{数据对象：D={ai| ai∈ElemSet,i=1,2,3……，n,n≥0}数据关系：R1={
