1、 本科生课程设计论文 题 目：图的遍历 2013 年年 07 月月 05 日日 1 课程设计任务课程设计任务书书 课程名称 数据结构课程设计 设计题目 图的遍历 指导教师 时间 2013.6.242013.7.5 一、教学要求 1. 掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力 2. 初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能 3. 提高综合运用所学的理论知识和方法独立分析和解决问题的能力 4. 训练用系统的观点和软件开发一般规范进行软件开发，培养软件工作者所应具备的科学的工作方 法和作风 二、设计资料及参数 每个学生在教师提供的课程设计题目中任意选
2、择一题，独立完成，题目选定后不可更换。 图的遍历：以数组表示法或邻接表表示图，在此基础上实现对图的遍历。 要求设计类（或类模板）来描述图，包含必要的构造函数和析构函数，以及其他能够完成如下功能的 成员函数： 输入图、输出图 求图中顶点 V 的第一个邻接点 求图中顶点 V 的下一个邻接点 深度优先遍历图 广度优先遍历图 并设计主函数测试该类（或类模板）。 三、设计要求及成果 1. 分析课程设计题目的要求 2. 写出详细设计说明 3. 编写程序代码，调试程序使其能正确运行 4. 设计完成的软件要便于操作和使用 5. 设计完成后提交课程设计报告 四、进度安排 资料查阅与讨论（1 天） 系统分析（2
3、天） 系统的开发与测试（5 天） 编写课程设计说明书和验收（2 天） 五、评分标准 1. 根据平时上机考勤、表现和进度，教师将每天点名和检查 2. 根据课程设计完成情况，必须有可运行的软件。 3. 根据课程设计报告的质量，如有雷同，则所有雷同的所有人均判为不及格。 4. 根据答辩的情况，应能够以清晰的思路和准确、简练的语言叙述自己的设计和回答教师的提问 六、建议参考资料 1数据结构（C 语言版）严蔚敏、吴伟民主编清华大学出版社 2004.11 2数据结构课程设计案例精编（用 C/C+描述），李建学 等 编著，清华大学出版社 2007.2 3.数据结构:用面向对象方法与 C+语言描述，殷人昆主编
4、， 清华大学出版社 2007.6 2 目录目录 第一章 图的遍历原理 . 4 1.1 总述 4 1.2 深度优先遍历 4 1.3 广度优先遍历 4 第二章 需求分析 . 5 第三章 总体设计 5 3.1 程序设计思路 5 3.2 功能视图. 6 第四章 类的设计 6 4.1 GraphUDN 类的设计 7 4.2 Queue 类的设计 8 第五章 详细设计 8 5.1 工程视图和类视图. 8 5.2 主要算法的流程图. 9 5.2.1 主函数的流程图 9 5.2.2 深搜流程图 10 5.2.3 广搜流程图 11 第六章 测试 13 6.1 菜单界面. 13 6.2 创建无向网. 13 6.3
5、 输出图. 14 6.4 输出顶点 V 的第一个邻接点 15 6.5 输出顶点 V 的下一个邻接点 15 6.6 深搜. 16 6.7 广搜. 16 3 第七章 总结 17 附录：程序代码 19 参考文献 27 4 第一章第一章 图的遍历原理图的遍历原理 1.1 总述总述 图的遍历：从图中某一顶点出发访遍图中其余顶点，且使得每一个顶点仅被 访问一次。这一过程就叫做图的遍历。 1.2 深度优先遍历深度优先遍历 深度优先遍历类似于树的先根遍历，是树的先根遍历的推广。 假如初始状态是图中所有顶点未曾被访问， 则深度优先遍历可从图中某个顶 点V出发， 访问此顶点， 然后依次从V的未被访问的邻接点出发深
6、度优先遍历图， 直到图中所有和 V 有路径相通的顶点都被访问到； 若图中此时尚有顶点未被访问， 则另选图中一个未曾被访问的顶点作起始点，重复上述过程，直到图中所有顶点 都被访问到为止。 以图 1.1 为例，假如从顶点 V1 出发进行搜索，在访问了顶点 V1 之后，选择 邻接点 V2。因为 V2 未曾访问，则从 V2 出发进行搜索。以此类推，接着从 V4， V8，V5 出发进行搜索。在访问了 V5 之后，由于 V5 的邻接点都已被访问，则搜 索回到 V8。由于同样的理由，搜索回到 V4，V2 直到 V1，此时由于 V1 的另一个 邻接点未被访问，则搜索又从 V1 到 V3，再继续进行下去。由此，得到的顶点访 问序列为： V1V2V4V8V5V3V6V7 1.3 广度优先遍历广度优先遍历 广度优先遍历类似于树的按层次遍历的过程。 假如从图中某顶点 V 出发，在访问了 V 之后依次访问 V 的各个未曾访问过 的邻接点，然后分别从这些邻接点出发依次访问它们的邻接点，并使“先被访问 5 的顶点的邻接点”先于“后被访问的顶点的邻接点”
