1、 学年论文（设计）学年论文（设计） （本科）（本科） 学 院 计算机与信息技术学院 专 业 信息管理与信息系统 年 级 姓 名 论文（设计）题目 图的遍历的实现 指导教师 职称 副教授 学生签名： 年 月 日 目录目录 一需求分析.错错 误误!未定义书签。未定义书签。 二、 概要设计2 三、详细设计3 四、调试分析及测试6 五、总结8 参考文献.9 附录11 一、一、 需求分析需求分析 为了进一步的了解图的遍历的问题，图的DFS,BFS 的递归和非递归算法的实现， 用有向图和无向图来实现图的遍历，用邻接矩阵和邻接表的存储方式存储图。 初 步掌握软件开发过程的问题分析、 系统设计、 程序编码、
2、测试等基本方法和技能。 训练我们灵活应用所学数据结构的基本知识，熟练的完成问题分析、算法设计、 编写程序，求解出指定的问题。训练用系统的观点和软件开发一般规范进行软件 开发，巩固、深化学生的理论知识，提高编程水平，并在此过程中培养严谨的科 学态度和良好的工作作风， 且提高综合运用所学的理论知识和方法独立分析和解 决问题的能力。 1.1 选择题目选择题目 【问题描述问题描述】 对给定的有向图或无向图，实现深度优先遍历及广度优先遍历。 【基本要求基本要求】 （1）先任意创建一个图； （2）图的 DFS,BFS 的递归和非递归算法的实现 （3）要求用有向图和无向图分别实现 （4）要求用邻接矩阵、邻接
3、表多种结构存储实现 1.21.2 功能需求功能需求 图的遍历并不需要是一个过于复杂的工作环境，一般来说：最合适的才是最 好的。软件设计必须符合我们使用实际情况的需要。根据要求，图的遍历主要功 能如下： 1、用户可以随时建立一个有向图或无向图； 2、用户可以根据自己的需要，对图进行深度遍历或广度遍历； 3、用户可以根据自己的需要对图进行修改； 二、概要设计二、概要设计 采用邻接矩阵作为图的存储结构。程序中主要用到以下抽象数据类型： 抽象数据类型的定义 typedef struct char *vexs; /顶点向量 int arcsMAX_VEXMAX_VEX; /邻接矩阵 int vexnum
4、,arcnum; /图的当前顶点数和弧数 Graph; 基本操作 CreateUDN(Graph 输入顶点数和弧数; 输入各个顶点及各条弧; 递归方法实现图的遍历： void DFS(Graph G, int k) 用递归的方法访问图中的结点; 对图进行深度优先遍历; 非递归方法实现图的遍历： void BFS(Graph G) 用队列辅助访问图中的结点; 对图进行广度优先遍历; 选择输出需要的遍历方法： void choose(Graph G) 给出程序运行的选项; 对相应的输入选项调用相应的函数以执行操作; 四、调试分析及测试四、调试分析及测试 在调试过程中，程序中出现了许多的错误，有错误
5、的调用、一些变量没有定 义、等等。不断的对程序进行调试以得到最好的结果，程序中特别要注意的是类 的对象作为作为参数时要注意如何去调用它，使程序有一个令人满意的结果，具 体的调试是在上机过程中进行的，在编写程序的过程中主要有如下错误： 1、在编写程序的过程出现了一些函数名、变量的大小写不统一的错误，导致 程序在运行的过程中出现函数名、变量没有被定义等问题； 2、在编写程序的过程中数组的大小写没有被确定； 3、在编写程序的过程中一些变量没有被定义，导致程序出错； 4、数组 visitedMax应定义为全局变量，若不是则会出错； 5、函数的返回类型要确定，是 void 还是其他类型要十分注意； 6、
6、在编程的过程中，函数里一些控制语句的嵌套使用，括号要引起注意， 这次的课程设计就有一些括号漏了或者多打了，导致括号不配套； 运行结果： 图图 3 3 输入图的顶点数和弧数输入图的顶点数和弧数 图图 4 4 输入各个顶点和各条弧输入各个顶点和各条弧 图图 5 5 选择图的遍历方式选择图的遍历方式 五、总结五、总结 通过这次课程设计，我受益颇多： 首先，上课时听的理论知识，似乎很容易接受，以及各种算法都能够比较轻 松的理解， 但是在真正的运用过程中， 并不能把理论知道很好的和实践结合起来。 感觉自己有点眼高手低，有些知识点的应用只有在实践中才能慢慢体会，在平时 做实验时，总感到有些无从下手。因此，在学知识的过程中，一定要多动手、动 脑，将所学的知识熟练掌握，
