深度与广度优先搜索迷宫问题讲解

1、LU 数据结构课程设计报告 题目：深度与广度优先搜索 -迷宫问题 专业计算机科学与技术 学生姓名 班级B计算机115 学号1110704512 2013年1月11日 指导教师巩永旺 完成日期 程序实践报告（2010） 目 录 1简介1 2算法说明1 3测试结果3 4分析与探讨7 5小结8 附 录10 附录1源程序清单10 程序实践报告（2010） 迷宫问题 1简介 1、图的存储结构 图的存储结构乂称图的表示，其最常用的方法是邻接矩阵和邻接表。无论采用 什么存储方式，其目标总是相同的，既不仅要存储图中各个顶点的信息，同时还要 存储顶点之间的所有关系。 2、图的遍历 图的遍历就是从指定的某个顶点（

2、称其为初始点）出发，按照一定的搜索方法 对图中的所有顶点各做一次访问过程。根据搜索方法不同，遍历一般分为深度优先 搜索遍历和广度优先搜索遍历。 本实验中用到的是广度优先搜索遍历。即首先访问初始点Vi,并将其标记为己 访问过，接着访问Vi的所有未被访问过的邻接点，顺序任意，并均标记为己访问过, 以此类推，直到图中所有和初始点Vi有路径相通的顶点都被访问过为止。鉴于广度 优先搜索是将所有路径同时按照顺序遍历，直到遍历出迷宫出口，生成的路径为最 短路径。因此我们采用了广度优先搜索。 无论是深度优先搜索还是广度优先搜索，其本质都是将图的二维顶点结构线性 化的过程，并将当前顶点相邻的未被访问的顶点作为下

3、一个顶点。广度优先搜索采 用队列作为数据结构。 本实验的目的是设计一个程序，实现手动或者自动生成一个nXm矩阵的迷宫, 寻找一条从入口点到出口点的通路。具体实验内容如下： 选择手动或者自动生成一个nXm的迷宫，将迷宫的左上角作入口，右下角作 出口，设“0”为通路，“1”为墙，即无法穿越。假设一只老鼠从起点出发，目的 为右下角终点，可向“上、下、左、右、左上、左下、右上、右下”8个方向行走。 如果迷宫可以走通，则用“”代表“1”，用“”代表“0”，用“”代表行 走迷宫的路径。输出迷宫原型图、迷宫路线图以及迷宫行走路径。如果迷宫为死迷 宫，则只输出迷宫原型图。 2算法说明 迷宫中存在通路和障碍，为

4、了方便迷宫的创建，可用o表示通路，用1表示障 碍，这样迷宫就可以用0、1矩阵來描述。设置迷宫的长为n、宽为m,范围为49 X49,用int mazeN十2M十2來表示，这样相当于在迷宫外层包了一层1,即防止 搜索路径时跳出迷宫。 （1）手动生成迷宫 程序实践报告（2010） void hand_maze(int m,int n) int i,j; fbr(i=0;im;i+) for(j=0;jn;j-H-) cmmazeij; (2)自动生成迷宫 void automatic_maze(mt m,iiit n) int i,j; fbi(i=0;im;i+) for(j=0；jn；j+) m

5、azeij=rand()%2; maze00=0; 为0,保证有可能出來迷宫 maze m-ln-l=0; 手动生成迷宫 自动生成迷宫 随机生成0、1 将开始和结束位置强制 2、迷宫路径的搜索 在生成的0、1矩阵迷宫中，首先从迷宫的入口开始，如果该位置就是迷宫出 口，则己经找到了一条路径，搜索工作结束。否则搜索其北（-1, 0）,东北（-1, 1）,东（0,1）,东南（1,1）,南（1,0）,西南（1, -1）,西（0, -1）,西北 （-1, -1） 8个方向位，是否是障碍，若不是障碍，就移动到该位置，然后再从该 位置开始搜索通往出口的路径；若是障碍就选择另一个相邻的位置，并从它开始搜 索路

6、径。为防止搜索重复出现，则将己搜索过的位置标记为2,同时保留搜索痕迹, 在考虑进入下一个位置搜索之前，将当前位置保存在一个队列中，如果所有相邻的 非障碍位置均被搜索过，且未找到通往出口的路径，则表明不存在从入口到出口的 路径。这实现的是广度优先遍历的算法，如果找到路径，则为最短路径。逆序输出 路径，将已输出的路径标记为3。 实验数据如下： 程序实跋报告（2010） 表3.1方向move的偏移量 Name du Movedif.vert Movedii.honz N 0 -1 0 NE 1 -1 1 E 2 0 1 SE 3 1 1 S 4 1 0 SW 5 1 -1 W 6 0 -1 NW 6

7、 0 -1 3测试结果 宫宫 迷迷 成成 生4 动动岀 手目退 蠱S: 请请请 12 3 请选择你的操作, 1 U输入疔数；8 请输入列数 8 请按行输入迷宫、 0表示通路, 1表示障咼: 1 0 i 0 0 1 0 10 0 0 10010110 1 0 1 1 0 0. 0 0 0 0 程序实践报告（2010） 图2 图3 程序实跋报告（2010） -|g|x| 4 15.3 t t C3r2 Cl,l 屣宫通眛用表示如下所示: 老:gH: 图4 C:UsNsAdministratorDesktop 李柏 111004512Debug 谜篡exf 欢迎进人迷宫求解系统 设计者二李柏（B计算

8、机115班） 12 3 按按拯 请请请 宫宫 迷迷 成成 生生 动动屮 手星 * X)C3X)C3XX3XX3XX3XX3XX3XX3KX3KX3KX3CKX3CKX3CKX)CKX)CKX)CKX)CKX)CKX)C1X)C1X)C1X)C3X)C3X)C3XX3XX3X 请选择你的操作: 2 请输入行数：8 请输入列数；8 迷宫生成中 请按任意键继续 程用实践报告（2010） CiXUserHAcIministfatOFDesktop、李柏！11004512Debug 谜宫exe 请输入列数：8 迷宫生成中 请按任意犍继续 根据您先前设定的迷宫范围 我们将取所输入的前64个数生成迷宫 数字

9、迷宫生成结果如下： 迷宫入口 0 0 1 0 1 1 1 1 1 0 0 0 0 1 0 1 mazeij=l代表该点是墙, 无法通行。 （4）迷宫有两种生成方式：手工设定和自动生成。 （5）当老鼠处于迷宫中某一点的位置上，它可以向8个方向前进，分别是：“上、 下、左、右、左上、左下、右上、右下”8个方向。 （6）要实现这个程序，首先要考虑如何表示这个迷宫。在实例程序中使用二维数 组mazefN十2N十2來表示这个迷宫，其中N为迷宫的行、列数。当值为“0” 时表示该点是通路，当值为“1”时表示该点是墙。老鼠在迷宫的位置在任何 时候都可以由行号iow和列号cool表示。 （7）为什么指定：maz

10、eN十2N十2來表示迷宫，而不是使用mazeNN表示迷 宫？原因是当老鼠跑到了迷宫的边界点时就有可能跳出迷宫，而使用 mazeN+2N+2就可以把迷宫的外边再包一层“1” ,这样就能阻止老鼠走 出格。 （8）老鼠在每一点都有8种方向可以走，分别是:North,NonliEast,East,SoutliEast, South,SouthWest,West, NonhWesto可以用数组move8來表示每一个方向上的横纵 坐标的偏移量，见表3.1。根据这个数组，就很容易计算出沿某个方向行走后的下 一个点的坐标。 方向move的偏移量 Name du Movedii.veit Movedii.hon

11、z N 0 -1 0 NE 1 -1 1 E 2 0 1 SE 3 1 1 S 4 1 0 SW 5 1 -1 W 6 0 -1 NW 6 0 -1 迷宫问题可以用深度优先搜索方法实现。当老鼠在迷宫中移动的时候，可能 会有许多种移动选择方向。程序需要记录并用栈來保存当前点的坐标，然后任意选 择一个方向进行移动。由于应用栈保存了当前通道上各点的坐标，所以当在当前各 程序实践报告(2010) 方向上都走不通时可以返回上一个点，然后选择另一个方向前进。 可定义element结构用于存储每一步的横纵坐标和方向。 tvpedef struct short int low; short int col;

12、short int dir; element; Element stackMAX _STACK_SIZE; 根据表3.1可推算出每次移动后的坐标。设当前的坐标是dow,col),移动的方向是 dir,移动后的点是next,则有 next_iow=row+move dir .veit; next_col=col+movedir.honz; 可用另一个二维数组maikN+2來记录哪些点己经被访问过。当经过点 maze row col时，相应地将 maikrow col的值从 0 置为 1。 本程序支持自动生成迷宫。利用landom (2)函数可随机产生0或1,來支持迷 宫的自动生成。注意mazeN

13、N和mazell定要等于0,因为他们分别是起点 和终点。 如果找到了一条走出迷宫的路径，则需要在屏幕中打印出如图3.5所示格式的信 息。这里要用到giaphics.il即TC中的图形库(注意：本程序是TC的实现，而 VC十十有自己的图形库，所以使用VC卄编译提示错误)。针对图3.5,可使用circle ()函数画圆，outtexttxy ()函数标记文字，并用line ()函数来划线。 程序的主要函数如下： 函数void add (int*top,element item),将当前步的信息item压入到作为全局变 量的栈stack (栈顶为top)中。 函数element delete (in

14、t * top),返回stack中栈顶的元素。 函数void path (void),釆用深度优先搜索算法，首先取出栈顶元素作为当前 点选择一个方向前进到下一个点(如果能走得话)；然后，将下一个点压入栈, 并将二维数组mm-k中对应的值改为1,表示该点己经走到了。反复执行上面两 步，当走到一个点不能再走下去了(已经尝试了各个方向并失败)，并且这个 点不是终点，则这个点的上一个点会从栈中被跑抛出，从而“回朔”到上一点; 当遇到终点时，程序结束，找到一条路径；当在程序循环过程中遇到栈为空， 则说明该迷宫根本无法走到终点。 5小结 为期一个星期的数据结构课程设计快结束了，这使我对深度和广度优先搜 索

15、有了更加深刻的理解和认识。我们团队负责的迷宫问题的课程设计就是充分 的利用深度和广度优先搜索的有关知识，主要运用的是广度优先搜索遍历。 程序实践报告（2010） （1）深度优先搜索遍历：深度优先搜索是一个递归过程。首先访问一个顶 点V1并将其标记为己访问过，然后从V1的任意一个未被访问的邻接点出发进 行深度优先搜索遍历。如此执行，当V1的所有邻接点均被访问过时，则退回到 上一个顶点Vk,从Vk的另一未被访问过的邻接点出发进行深度优先搜索遍历。 如此执行，直到退回到初始点并且没有未被访问过的邻接点为止。 （2）广度优先搜索遍历：广度优先搜索过程为：首先访问初始点Vi,并将 其标记为己访问过，接着

16、访问Vi的所有未被访问过的邻接点，其访问顺序可 以任意，假定依次为Vil、Vi2, -Vin,并标记为己访问过，然后按照Vil、 V12, !】的次序访问每一个顶点的所有未被访问过的邻接点，并均标记为己 访问过，依次类推，直到图中所有和初始点Vi有路径相通的顶点都被访问过 为止。在设计迷宫问题时要考虑使用二维数组，在数组中我们选择 mazeN+2N+2來表示迷宫，而不是用mazeNN来表示，这样就可以避免老 鼠走迷宫会出格。 通过这一个星期的学习实践，我更加深层次的了解了关于数据结构的相关 知识，也越來越发现自己对数据结构方面知识的欠缺，使我对自己所学得的知 识有了一个深刻的理解，对于这方面的

17、知识，我还缺少很多，纸上得來终觉浅, 再强大的理论也要通过实践来证明。在今后的学习中我要多练习，做一个专业 的计算机学生。 程序实践报告（2010） 参考文献 11刘振安,刘燕君.C程序设计课程设计M.北京机械工业出版社,2004年9月 2谭浩强.C程序设计（第三版）.清华大学出版社,2005年7月 3严蔚敏，吴伟民.数据结构（C语言版）.清华大学出版社，1997年4月 4李志球实用C语言程序设计教程北京：电子工业出版社，1999 5王立柱：C/C+与数据结构 北京：清华大学出版社，2002 6吴文虎程序设计基础北京：清华大学出版社，2003 7郭福顺，王晓芬，李莲治 数据结构（修订本），大连

18、理工大学出版社, 1997 8潘道才，陈一华数据结构,电子科技大学出版社，1994 10 程序实践报告（2010） 附 录 附录1源程序清单 # mclude # mclude # mclude using namespace std; define N 49 以自行修改 #define M 49 intX; int mazeN+2M+2; int head=0Jail=0; stmct point 列，行，序号 mt row,col,predecessor; queue1200; void haiid_maze(mt m.iiit n) mt ij； coutendl; 库中包含svstem

19、Cpause）和rand（）函数 /c语言里的库 定义为全局变量,这是迷宫数组的上线，可 队列的头尾指针，初始值设为0 存放迷宫访问到点的队列结构体，包含 手动生成迷宫 程序实践报告(2010) coutH请按行输入迷宫，0表示通路，1表示障碍:Hendl; for(j=0;jnj+) cinniazeij; j /自动生成迷宫 随机生成0. 1 将开始和结束位置强制为0,保证有可 void autoniatic_niaze(mt mjnt n) Hit 1J； coutHn迷宫生成中nnM; system(HpauseH); fbi(i=0;im;i+) for(j=OJnj+) maze

20、i j=rand()%2; maze00=0; 能出来迷宫 mazem-ln-l=0: void data(int m.mt n) 当用户输入的不是规整的m行n列的迷宫，用来生成规则 的数字迷宫 mt ij； coutendl; cout根据您先前设定的迷宫范WHendl; coutendl; coutM我们将取所输入的HUnm*nM个数生成迷宫Hendl; coutHn数字迷宫生成结果如下:nn”； coutH 迷宫入 IIS; coutn I ”； fbr(i=0;im;i+) coutHnM; for(j=Ojn;j+) if(mazeij=0) coutH 0”； if(mazeij=

21、l) coutn T： coutvvJ 迷宫出nM; void prmt_maze(int m.mt n) 打印迷宫外壳 int ij,k; coutn字符迷宫生成结果如下Ann”； coutH 迷宫入 IIS; coutH I ”； coutendl; 生成上外壳 coutHA 12 程序实践报告（2010） for(k=0;kn;k+) coutMA,r; fbr(i=0;im;i+) coutHnM; coutMA,r; for(j=0jn;j+) if(inazeij=0) prmtf(nnn); if(inazeij=l) piiiitf(nHH); coutMA,r; couten

22、dl; for(k=0;kn;k+) coutMA,r; coutH coutM ”; coutH I nM; fbr(i=0;in;i-H-) coutM ”; coutH迷宫出 I IE; void result_niaze(intn) 径 mt ij； coutM迷宫通路(用表示)如下所示：nt”; fbi(i=0;im;i+) coutHnM; for(j=Oj=0)东北 if(p.iow-r0)m)I你 if(p.iow+1 )m)东南 if(p.iow+l)m)南 14 程序实践报告（2010） if(p.row+1 )m)西南 if(p.row+0)m)西 if(p.row-1

23、)=0)西 d 匕 if(p.ro=m-l coutM MM t Hendl; printf(H(%d,%d)irp.row+l,p.col+l); coutM MM t Hendl; 逆序将路径标记为3 mazep.rowp.col=3; while(p.predecessoi!=-l) p=queuep.predecessor; pnntf(”(d,%d)ir,pow+l,pcol+l); coutM nM t ,rendl; maze p. row p.col=3; coutH入 I lHendl; else coutHn=aiH; coutM此迷宫无解！ niiM; X=0; return 0; void niaiii() mt imii,cycle=0; while(cycle !=(-!) 手动生成迷宫请按:ln-; *n coutH coutendl; 欢迎进入迷宫求解系统n”； coutH 设计者:李柏（e计算机115班）ir； *n coutH 15 程序实践报告(2010) coutH coutH 自动生成迷宫请按：2nM; coutHnH; coutH请选择你的操作：n”; ciiii; switch(i) 退出请按：3niT; case 1: coutMn请输入行数：”； cinm;