数据结构课程实验报告
课程名称 姓名 实验名称 实 验 目 的 及 要 求 数据结构 班级 学号 计算123 实验日期 实验成绩 2014年6月1日--3日 实验四 图的深度和广度优先遍历 【实验目的】 熟练掌握图的邻接表存储结构及其图的建立方法和深度和广度优先遍历的方法。 【实验要求】 1. 图的存储可采用邻接矩阵或邻接表 2. GraphCreate(): 按从键盘的数据建立图 3. GraphDFS()：深度优先遍历图 4. GraphBFS()：广度优先遍历图 5. 编写完整程序完成下面的实验内容并上机运行 6. 整理并上交实验报告 硬件平台：普通的PC机 软件平台：Windows 7 操作系统 编程环境：VisualC++ 6.0 实 验 环 境 实 验 内 容 1.以邻接矩阵或邻接表为存储结构，以用户指定的顶点为起始点，实现图的深度优先及广度优先搜索遍历，并输出遍历的结点序列。 1
算 法 描 述 及 实 验 步 骤 算法： 1)定义图的邻接表存储结构 2）实现图的邻接表存储，即建立图的存储结构 3）实现图的深度优先遍历 4）定义队列的顺序存储结构，并实现队列的基本操作如初始化队列、入队、出对、判断队列是否为空等。利用队列实现图的广度优先遍历。 伪代码： 1） 定义邻接矩阵和队列的存取结构； 2） 创建图L： 1. 置空图L->num=0； 2. 输入顶点数目num； 3. i++,输入结点L->vexs[i]直到L->num; 3） 输出图L的各顶点； 4） 深度优先遍历图g中能访问的各个顶点 1. 输入起点的下标qidian； 2. 标志数组初始化mark[v]=0; 3. for(v=qidian;v 开始 访问V0,置标志 求V0邻接点 有邻接点w Y N 结束 Y W访问过 N w?V0 求下一邻接点 DFS 开始 标志数组初始化 Vi=1 Vi访问过 N DFS Y Vi=Vi+1 Vi==Vexnums N Y 结束 3