数据结构课程设计
课题名称 深度与广度优先搜索：迷宫问题
专业 计算机科学与技术
沈涛 B计122 1210704218
学生姓名 班学
级 号
目 录
1 简介 .......................................................................................................................... 1 2 算法说明 ................................................................................................................. 1 3测试结果 ................................................................................................................. 2 3.1 测试输入 ............................................................................................................. 2 3.2 测试目的 ............................................................................................................. 2 3.3 正确输出 ............................................................................................................. 2 3.4 实际输出 ............................................................................................................. 2 4 分析与探讨 ............................................................................................................. 2 4.1 测试结果分析 ..................................................................................................... 2 4.2 探讨与改进 ......................................................................................................... 3 附录：源代码 ............................................................................................................ 3
目录生成的方式为：右击，在快捷菜单中选择“更新域”，在“更新目录”对话框中选择“更新整个目录”。接着选中目录内容，修改字体和字号，中文选择宋体四号，不加粗；英文字体选择Times New Romman，四号，不加粗。再修改段落，行间距为25磅。其余项默认即可
1 简介 深度优先搜索（Depth_First Search,简称DFC）是一个递归过程。首先访问一个顶点vi并将其标记为已访问过，然后从vi的任意一个未被访问的邻接点出发进行深度优先搜索遍历。如此执行，当vi的所有邻接点均被访问过时，则退回到上一个顶点vk,从vk的另一未被访问过的邻接点出发进行深度优先搜索遍历。如此执行，直到退回到初始点并且没有未被访问过的邻接点为止。
广度优先搜索（Breadth-First-Search,简称BFS）过程为：首先访问初始点vi,并将其标记为已访问过，接着访问vi的所有未被访问过的邻接点，其访问顺序可以任意，假定依次为vi1,vi2,„,vin,并均标记为已访问过，然后再按照vi1,vi2,„,vin的次序，访问每一个顶点的所有未被访问的邻接点，并标记为已访问过，以此类推，直到图中所有和初始点vi有路径相通的顶点都被访问过为止。
比较两者过程可以发现一个共同点是，总以某个已被访问过的顶点作为当前顶点来搜索与其相邻的未被访问的顶点。而区别仅在于对当前顶点的选择策略有所不同，BFS总是优先选择最早访问的顶点作为当前顶点来搜索邻接点，而DFS则是将优先选择最近访问顶点作为当前顶点来搜索邻接点。
无论是深度优先搜索还是广度优先搜索，其本质都是将图的二维顶点结构线性化的过程，并将当前顶点相邻的未被访问顶点作为下一个顶点。由于与当前顶点相邻的顶点可能多于一个，而每次只能选择其中的一个作为下一个顶点，这样势必要保存其他相邻顶点。深度优先搜索和广度优先搜索在数据结构上的区别就在于用于保存其它相邻顶点的方式不同，深度优先搜索采用栈，而广度优先搜索则采用队列。从形式上，深度优先搜索往往采用一个递归过程，实际上递归的编译实现就应用了栈。 2 算法说明
@@@@@。
1
3测试结果
3.1 测试输入
一般的迷宫可表示为一个二维平面图形，将迷宫的左上角作入口，右下角作出口。迷宫问题求解的目标是寻找一条从入口点到出口点的通路。
例如，可以设计一个8*8矩阵maze[8][8]来表示迷宫，如下所示： 0 1 0 0 0 0 1 1 0 0 0 1 0 0 1 0 1 0 1 0 1 0 1 1 1 0 1 0 1 1 0 1 0 1 1 1 1 1 1 0 1 0 0 1 1 0 0 0 1 0 1 0 0 0 1 1 1 0 1 1 0 1 0 0
左上角maze[0][0]为起点，右下角maze[7][7]为终点；设“0”为通路，“1”为墙，即无法穿越。假设一只老鼠从起点出发，目的为右下角终点，可向“上、下、左、右、左上、左下、右上、右下”8个方向行走。
3.2 测试目的
请设计一个程序，能自动生成或者手动生成这样一个8*8矩阵，针对这个矩阵，程序判断是否能从起点经过迷宫走到终点。如果不能，请指出；如果能，请用图形界面标出走出迷宫的路径。
3.3 正确输出
@@@@@。 3.4 实际输出
@@@@@。
4 分析与探讨
4.1 测试结果分析
@@@@@。
2
4.2 探讨与改进
附录：源代码
@@@@@。
3
