图的深度优先遍历算法课程设计报告.pdfVIP

合肥学院 计算机科学与技术系 课程设计报告 2013～2014 学年 第二学期 课 程 数据结构与算法 课 程 设 计 名 称 图的深度优先遍历算法的实现 学 生 姓 名 陈琳 学 号 1204091022 专 业 班 级 软件工程 指 导 教 师 何立新 2014 年 9 月 一：问题分析和任务定义 涉及到数据结构遍会涉及到对应存储方法的遍历问题。本次程序采用邻接表的存储方 法，并且以深度优先实现遍历的过程得到其遍历序列。 深度优先遍历图的方法是，从图中某顶点 v 出发： （1 ）访问顶点 v ； （2 ）依次从 v 的未被访问的邻接点出发，对图进行深度优先遍历；直至图中和 v 有路径相 通的顶点都被访问； （3 ）若此时图中尚有顶点未被访问，则从一个未被访问的顶点出发，重新进行深度优先遍 历，直到图中所有顶点均被访问过为止。 二：数据结构的选择和概要设计 设计流程如图： 深 度 创 建 创 建 优 先 邻 接 图 遍历 表 图 1 设计流程 利用一维数组创建邻接表， 同时还需要一个一维数组来存储顶点信息。 之后利用创建的 邻接表来创建图，最后用深度优先的方法来实现遍历。 深度优先遍历是连通图的一种遍历策略。其基本思想如下： 设 x 是当前被访问顶点， 在对 x 做过访问标记后， 选择一条从 x 出发的未检测过的边 (x ， y) 。若发现顶点 y 已访问过，则重新选择另一条从 x 出发的未检测过的边，否则沿边 (x ，y) 到达未曾访问过的 y，对 y 访问并将其标记为已访问过；然后从 y 开始有哪些信誉好的足球投注网站，直到有哪些信誉好的足球投注网站完从 y 出发的所有路径，即访问完所有从 y 出发可达的顶点之后，才回溯到顶点 x ，并且再选择 一条从 x 出发的未检测过的边。上述过程直至从 x 出发的所有边都已检测过为止。 例如下图中（既本次设计用到的图）： 0 2 1 4 3 图 2 原始图 1. 从 0 开始，首先找到 0 的关联顶点 3 2. 由 3 出发，找到 1；由 1 出发，没有关联的顶点。