1、 * 实践教学实践教学 * 计算机与通信学院 2012 年春季学期 算法与数据结构算法与数据结构 课程设计课程设计 题 目：图的遍历和生成树的求解实现 专业班级：计算机科学与技术 姓 名： * 学 号： 1234567 指导教师： * 成 绩： 目目 录录 摘摘 要要 3 前前 言言 4 正正 文文 5 1.问题描述：问题描述： . 5 2.采用类采用类 C 语言定义相关的数据类型语言定义相关的数据类型 5 3各模块流程图及伪码算法各模块流程图及伪码算法 6 4函数的调用关系图函数的调用关系图 8 5调试分析调试分析 9 1.调试中遇到的问题及对问题的解决方法 9 2.算法的时间复杂度和空间复
2、杂度 9 6.测试结果测试结果 . 10 参考文献参考文献 14 摘摘 要要 图是一种复杂的非线性数据结构，一个图 G（Grah）由两个集合 V 和 E 构成，图存在两种遍历方式，深度优先遍历和广度优先遍历，广度优先遍历 基本思路是假设从图中某顶点 U 出发，在访问了顶点 U 之后依次访问 U 的各个未 访问的领接点，然后分别从这些领接点出发依次访问他们的领接点，并使先访问 的顶点的领接点先于后访问的顶点被访问。直至所有领接点被访问到。深度优先 的基本思路是从某个顶点出发，访问此顶点，然后依次从 V 的未被访问的领接点 出发深度优先检索土。直至图中所有顶点都被访问到。PRIM 算法KRUSKA
3、L 算法； 可以对图形进行最小生成树的求解。 主要问题是： （1）当给出一个表达式时，如何创建图所表达的树，即相应的逻辑结构和存 储结构？ （2）表达式建立好以后，如何求出其遍历？深度优先和广度优先遍历。 （3）计算它的最小生成树？主要是 prim算法和 kruscal 算法两种形式。 前前 言言 很多涉及图的操作的算法都是以图的遍历操作为基础，通过遍历的演示，方 便在学习中更好的理解突地遍历的过程。 通过对图的深度优先遍历和广度优先遍历的演示，分别两种遍历的不同与其 优缺点。 我们在对一些问题进行求解时，会发现有些问题很难找到规律，或者根本无 规律可寻。对于这样的问题，可以利用计算机运算速度
4、快的特点，先搜索查找所 有可能出现的情况，再根据题目条件从所有可能的情况中，删除那些不符合条件 的解。 在深度优先搜索算法中，是深度越大的结点越先得到扩展。如果在搜索中把 算法改为按结点的层次进行搜索， 本层的结点没有搜索处理完时，不能对下层结 点进行处理，即深度越小的结点越先得到扩展， 也就是说先产生 的结点先得以 扩展处理，这种搜索算法称为广度优先搜索法。很多问题都可以用广度优先搜索 进行处理，如翻币问题、最短路径问题等。 在计算机中，有多种方法存储图的信息，由于图的结构复杂，使用广泛，一 般应根据实际的应用，选择适合的表示方法。常用的图的存储结构有邻接矩阵、 邻接多重表和邻接表。 在实际
5、问题当中，经常遇到这类问题，为新建的某个机构进行选址，道路交 通路线，如何走完所有路线，旅游线路等一系列问题都涉及到图的知识。图是一 种复杂的非线性数据结构，一个图 G（Grah）由两个集合 V 和 E。 构成，图存在两种遍历方式，深度优先遍历和广度优先遍历，广度优先遍历 基本思路是假设从图中某顶点 U 出发，在访问了顶点 U 之后依次访问 U 的各个未 访问的领接点，然后分别从这些领接点出发依次访问他们的领接点，并使先访问 的顶点的领接点先于后访问的顶点被访问。直至所有领接点被访问到。深度优先 的基本思路是从某个顶点出发，访问此顶点，然后依次从 V 的未被访问的领接点 出发深度优先检索图。直
6、至图中所有顶点都被访问到。PRIM 算法KRUSKAL 算法； 可以对图形进行最小生成树的求解。 树型结构是一种非线性结构，它用于描述数据元素之间层次关系，如人类社 会的族谱等，树型结构的应用非常广泛，磁盘文件目录结构就是一个典型的例子。 正正 文文 1.问题描述：问题描述： 图是一种复杂的非线性数据结构，一个图 G（Grah）由两个集合 V 和 E 构成，图存在两种遍历方式，深度优先遍历和广度优先遍历，广度优先遍历 基本思路是假设从图中某顶点 U 出发，在访问了顶点 U 之后依次访问 U 的各个未 访问的领接点，然后分别从这些领接点出发依次访问他们的领接点，并使先访问 的顶点的领接点先于后访问的顶点被访问。直至所有领接点被访问到。深度优先 的基本思路是从某个顶点出发，访问此顶点，然后依次从 V 的未被访问的领接点 出发深度优先检索土。直至图中所有顶点都被访问到。PRIM 算法KRUSKAL 算法； 可以对
