数据结构课程设计--图的遍历

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

1、内蒙古科技大学课程设计论文内蒙古科技大学本科生课程设计论文题目：图的遍历2013年07月05日27内蒙古科技大学课程设计论文内蒙古科技大学课程设计任务书课程名称数据结构课程设计设计题目图的遍历指导教师时间2013.6.24——2013.7.5一、教学要求1.掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力2.初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能3.提高综合运用所学的理论知识和方法独立分析和解决问题的能力4.训练用系统的观点和软件开发一般规范进行软件开发，培养软件工作者所应具备的科学的工作方法和作风二、设计资料及参数每个学生在教师提

2、供的课程设计题目中任意选择一题，独立完成，题目选定后不可更换。图的遍历：以数组表示法或邻接表表示图，在此基础上实现对图的遍历。要求设计类（或类模板）来描述图，包含必要的构造函数和析构函数，以及其他能够完成如下功能的成员函数：v输入图、输出图v求图中顶点V的第一个邻接点v求图中顶点V的下一个邻接点v深度优先遍历图v广度优先遍历图并设计主函数测试该类（或类模板）。三、设计要求及成果1.分析课程设计题目的要求2.写出详细设计说明3.编写程序代码，调试程序使其能正确运行4.设计完成的软件要便于操作和使用5.设计完成后提交课程设计报告四、进度安排资料查阅与讨论（1天）系统分析（2天）系

3、统的开发与测试（5天）编写课程设计说明书和验收（2天）五、评分标准1.根据平时上机考勤、表现和进度，教师将每天点名和检查2.根据课程设计完成情况，必须有可运行的软件。3.根据课程设计报告的质量，如有雷同，则所有雷同的所有人均判为不及格。4.根据答辩的情况，应能够以清晰的思路和准确、简练的语言叙述自己的设计和回答教师的提问六、建议参考资料1．《数据结构（C语言版）》严蔚敏、吴伟民主编清华大学出版社2004.112．《数据结构课程设计案例精编（用C/C++描述）》，李建学等编著，清华大学出版社2007.23.《数据结构:用面向对象方法与C++语言描述》，殷人昆主编， 清华大学出版

4、社2007.627内蒙古科技大学课程设计论文目录第一章图的遍历原理31.1总述31.2深度优先遍历31.3广度优先遍历4第二章需求分析4第三章总体设计53.1程序设计思路53.2功能视图5第四章类的设计64.1GraphUDN类的设计64.2Queue类的设计7第五章详细设计85.1工程视图和类视图85.2主要算法的流程图95.2.1主函数的流程图95.2.2深搜流程图105.2.3广搜流程图11第六章测试136.1菜单界面136.2创建无向网136.3输出图146.4输出顶点V的第一个邻接点156.5输出顶点V的下一个邻接点156.6深搜166.7广搜1627内蒙古科技大学

5、课程设计论文第七章总结16附录：程序代码18参考文献2727内蒙古科技大学课程设计论文第一章图的遍历原理1.1总述图的遍历：从图中某一顶点出发访遍图中其余顶点，且使得每一个顶点仅被访问一次。这一过程就叫做图的遍历。1.2深度优先遍历深度优先遍历类似于树的先根遍历，是树的先根遍历的推广。假如初始状态是图中所有顶点未曾被访问，则深度优先遍历可从图中某个顶点V出发，访问此顶点，然后依次从V的未被访问的邻接点出发深度优先遍历图，直到图中所有和V有路径相通的顶点都被访问到；若图中此时尚有顶点未被访问，则另选图中一个未曾被访问的顶点作起始点，重复上述过程，直到图中所有顶点都被访问到为止。

6、以图1.1为例，假如从顶点V1出发进行搜索，在访问了顶点V1之后，选择邻接点V2。因为V2未曾访问，则从V2出发进行搜索。以此类推，接着从V4，V8，V5出发进行搜索。在访问了V5之后，由于V5的邻接点都已被访问，则搜索回到V8。由于同样的理由，搜索回到V4，V2直到V1，此时由于V1的另一个邻接点未被访问，则搜索又从V1到V3，再继续进行下去。由此，得到的顶点访问序列为：V1—V2—V4—V8—V5—V3—V6—V71.3广度优先遍历广度优先遍历类似于树的按层次遍历的过程。假如从图中某顶点V出发，在访问了V之后依次访问V27内蒙古科技大学课程设计论文的各个未曾访问过的邻接点

7、，然后分别从这些邻接点出发依次访问它们的邻接点，并使“先被访问的顶点的邻接点”先于“后被访问的顶点的邻接点”被访问，直到图中所有已被访问的顶点的邻接点都被访问到。若图中此时尚有顶点未被访问，则另选图中一个未曾被访问的顶点作起始点，重复上述过程，直到图中所有顶点都被访问到为止。以图1.1为例，首先访问V1和V1的邻接点V2和V3，然后依次访问V2的邻接点V4和V5及V3的邻接点V6和V7，最后访问V4的邻接点V8。由于这些顶点的邻接点均已被访问，并且图中所有顶点都被访问，由此完成图的遍历。得到的顶点访问序