迷宫问题（maze problem）——深度优先（DFS）与广度优先 ...

迷宫问题的求解可以抽象为连通图的遍历，因此主要有两种方法。

第一种方法是：深度优先搜索（DFS）加回溯。

其优点：无需像广度优先搜索那样（BFS） ... 腾讯云备案控制台云+社区专栏视频精选问答沙龙云+竞赛实验室团队主页开发者手册腾讯云TI平台TVP搜索搜索关闭创作写文章发视频提问登录注册展开腾讯云·社区登录首页专栏视频精选问答沙龙云+竞赛团队主页开发者手册腾讯云TI平台TVP返回腾讯云官网Dabelv腾讯·后台开发工程师(已认证)614篇文章迷宫问题（mazeproblem）——深度优先（DFS）与广度优先搜索（BFS）求解转到我的清单专栏首页C/C++基础迷宫问题（mazeproblem）——深度优先（DFS）与广度优先搜索（BFS）求解21分享分享文章到朋友圈分享文章到QQ分享文章到微博复制文章链接到剪贴板海报分享海报分享迷宫问题（mazeproblem）——深度优先（DFS）与广度优先搜索（BFS）求解2018-08-032018-08-0314:56:27阅读6.1K01.问题简介给定一个迷宫，指明起点和终点，找出从起点出发到终点的有效可行路径，就是迷宫问题（mazeproblem）。

迷宫可以以二维数组来存储表示。

0表示通路，1表示障碍。

注意这里规定移动可以从上、下、左、右四方方向移动。

坐标以行和列表示，均从0开始，给定起点（0,0）和终点（4,4），迷宫表示如下：intmaze[5][5]={ {0,0,0,0,0}, {0,1,0,1,0}, {0,1,1,0,0}, {0,1,1,0,1}, {0,0,0,0,0} };那么下面的迷宫就有两条可行的路径，分别为： （1）(0,0)(0,1)(0,2)(0,3)(0,4)(1,4)(2,4)(2,3)(3,3)(4,3)(4,4)； （2）(0,0)(1,0)(2,0)(3,0)(4,0)(4,1)(4,2)(4,3)(4,4)；可见，迷宫可行路径有可能是多条，且路径长度可能不一。

2.求解方法迷宫问题的求解可以抽象为连通图的遍历，因此主要有两种方法。

第一种方法是：深度优先搜索（DFS）加回溯。

其优点：无需像广度优先搜索那样（BFS）记录前驱结点。

其缺点：找到的第一条可行路径不一定是最短路径，如果需要找到最短路径，那么需要找出所有可行路径后，再逐一比较，求出最短路径。

第二种方法是：广度优先搜索（BFS）。

其优点：找出的第一条路径就是最短路径。

其缺点：需要记录结点的前驱结点，来形成路径。

下面将给出上面两种方法的具体步骤和实现。

3.方法详解与具体实现3.1深度优先搜索（DFS）加回溯求解第一条可行路径3.1.1实现步骤（1）给定起点和终点，判断二者的合法性，如果不合法，返回； （2）如果起点和终点合法，将起点入栈； （3）取栈顶元素，求其邻接的未被访问的无障碍结点。

求如果有，记其为已访问，并入栈。

如果没有则回溯上一结点，具体做法是将当前栈顶元素出栈。

其中，求邻接无障碍结点的顺序可任意，本文实现是以上、右、下、左的顺序求解。

（4）重复步骤（3），直到栈空（没有找到可行路径）或者栈顶元素等于终点（找到第一条可行路径）。

3.1.2具体实现#include #include usingnamespacestd; structPoint{ //行与列 introw; intcol; Point(intx,inty){ this->row=x; this->col=y; } booloperator!=(constPoint&rhs){ if(this->row!=rhs.row||this->col!=rhs.col) returntrue; returnfalse; } }; //func:获取相邻未被访问的节点 //para:mark:结点标记，point：结点，m：行，n：列 //ret:邻接未被访问的结点 PointgetAdjacentNotVisitedNode(bool**mark,Pointpoint,intm,intn){ PointresP(-1,-1); if(point.row-1>=0&&mark[point.row-1][point.col]==false){//上节点满足条件 resP.row=point.row-1; resP.col=point.col; returnresP; } if(point.col+1=0&&mark[point.row][point.col-1]==false){//左节点满足条件 resP.row=point.row; resP.col=point.col-1; returnresP; } returnresP; } //func：给定二维迷宫，求可行路径 //para:maze：迷宫；m：行；n：列；startP：开始结点endP：结束结点；pointStack：栈，存放路径结点 //ret:无 voidmazePath(void*maze,intm,intn,constPoint&startP,PointendP,stack&pointStack){ //将给定的任意列数的二维数组还原为指针数组，以支持下标操作 int**maze2d=newint*[m]; for(inti=0;ipointStack; mazePath(maze,5,5,startP,endP,pointStack); //没有找打可行解 if(pointStack.empty()==true) cout<tmpStack; cout< #include #include usingnamespacestd; structPoint{ //行与列 introw; intcol; Point(intx,inty){ this->row=x; this->col=y; } booloperator!=(constPoint&rhs){ if(this->row!=rhs.row||this->col!=rhs.col) returntrue; returnfalse; } booloperator==(constPoint&rhs)const{ if(this->row==rhs.row&&this->col==rhs.col) returntrue; returnfalse; } }; intmaze[5][5]={ {0,0,0,0,0}, {0,-1,0,-1,0}, {0,-1,-1,0,0}, {0,-1,-1,0,-1}, {0,0,0,0,0} }; //func:获取相邻未被访问的节点 //para:mark:结点标记；point：结点；m：行；n：列;endP:终点 //ret:邻接未被访问的结点 PointgetAdjacentNotVisitedNode(int**mark,Pointpoint,intm,intn,PointendP){ PointresP(-1,-1); if(point.row-1>=0){ if(mark[point.row-1][point.col]==0||mark[point.row][point.col]+1=0){ if(mark[point.row][point.col-1]==0||mark[point.row][point.col]+1&pointStack,vector&vecPath){ //将给定的任意列数的二维数组还原为指针数组，以支持下标操作 int**maze2d=newint*[m]; for(inti=0;ivisitedEndPointPreNodeVec; //将起点入栈 pointStack.push(startP); mark[startP.row][startP.col]=true; //栈不空并且栈顶元素不为结束节点 while(pointStack.empty()==false){ PointadjacentNotVisitedNode=getAdjacentNotVisitedNode(mark,pointStack.top(),m,n,endP); if(adjacentNotVisitedNode.row==-1){//没有符合条件的相邻节点 pointStack.pop();//回溯到上一个节点 continue; } if(adjacentNotVisitedNode==endP){//以较短的路劲，找到了终点, mark[adjacentNotVisitedNode.row][adjacentNotVisitedNode.col]=mark[pointStack.top().row][pointStack.top().col]+1; pointStack.push(endP); stackpointStackTemp=pointStack; vecPath.clear(); while(pointStackTemp.empty()==false){ vecPath.push_back(pointStackTemp.top());//这里vecPath存放的是逆序路径 pointStackTemp.pop(); } pointStack.pop();//将终点出栈 continue; } //入栈并设置访问标志为true mark[adjacentNotVisitedNode.row][adjacentNotVisitedNode.col]=mark[pointStack.top().row][pointStack.top().col]+1; pointStack.push(adjacentNotVisitedNode); } } intmain(){ PointstartP(0,0); PointendP(4,4); stackpointStack; vectorvecPath; mazePath(maze,5,5,startP,endP,pointStack,vecPath); if(vecPath.empty()==true) cout<row,i->col); } getchar(); }程序输出最短路径如下： 如果将程序的迷宫改为如下:intmaze[5][3]={ 0,-1,0, 0,-1,0, 1,-1,0, 0,-1,0, 0,0,0};输出： 代码相关说明： 对比3.1.2的代码，根据改进的办法，可以看到上段代码修改的地方主要有三个地方： （1）mark标记改为结点权值，记录起点到结点的路径长度。

因此起点的权值为0。

（2）为适应mark标记，将迷宫的墙改为-1，以免与结点权值混淆。

（3）求解下一个访问的结点，判断条件是结点的权值要小于其当前权值。

3.3广度优先搜索（BFS）求解迷宫的最短路径广度优先搜索的优点是找出的第一条路径就是最短路径，所以经常用来搜索最短路径，思路和图的广度优先遍历一样，需要借助于队列。

具体步骤： （1）从入口元素开始，判断它上下左右的邻边元素是否满足条件，如果满足条件就入队列； （2）取队首元素并出队列。

寻找其相邻未被访问的元素，将其如队列并标记元素的前驱节点为队首元素。

（3）重复步骤（2），直到队列为空（没有找到可行路径）或者找到了终点。

最后从终点开始，根据节点的前驱节点找出一条最短的可行路径。

具体实现： 以C++为例：#include #include usingnamespacestd; structPoint{ //行与列 introw; intcol; //默认构造函数 Point(){ row=col=-1; } Point(intx,inty){ this->row=x; this->col=y; } booloperator==(constPoint&rhs)const{ if(this->row==rhs.row&&this->col==rhs.col) returntrue; returnfalse; } }; intmaze[5][5]={ {0,0,0,0,0}, {0,1,0,1,0}, {0,1,1,1,0}, {0,1,0,0,1}, {0,0,0,0,0} }; voidmazePath(void*maze,intm,intn,Point&startP,PointendP,vector&shortestPath){ int**maze2d=newint*[m]; for(inti=0;iqueuePoint; queuePoint.push(startP); //将起点的前驱节点设置为自己 mark[startP.row][startP.col]=startP; while(queuePoint.empty()==false){ PointpointFront=queuePoint.front(); queuePoint.pop(); if(pointFront.row-1>=0&&maze2d[pointFront.row-1][pointFront.col]==0){//上节点连通 if(mark[pointFront.row-1][pointFront.col]==Point()){//上节点未被访问，满足条件，如队列 mark[pointFront.row-1][pointFront.col]=pointFront; queuePoint.push(Point(pointFront.row-1,pointFront.col));//入栈 if(Point(pointFront.row-1,pointFront.col)==endP){//找到终点 break; } } } if(pointFront.col+1=0&&maze2d[pointFront.row][pointFront.col-1]==0){//左节点连通 if(mark[pointFront.row][pointFront.col-1]==Point()){//上节点未被访问，满足条件，如队列 mark[pointFront.row][pointFront.col-1]=pointFront; queuePoint.push(Point(pointFront.row,pointFront.col-1));//入栈 if(Point(pointFront.row,pointFront.col-1)==endP){//找到终点 break; } } } } if(queuePoint.empty()==false){ introw=endP.row; intcol=endP.col; shortestPath.push_back(endP); while(!(mark[row][col]==startP)){ shortestPath.push_back(mark[row][col]); row=mark[row][col].row; col=mark[row][col].col; } shortestPath.push_back(startP); } } intmain(){ PointstartP(0,0); PointendP(4,4); vectorvecPath; mazePath(maze,5,5,startP,endP,vecPath); if(vecPath.empty()==true) cout<row,i->col); } getchar(); }程序输出： 代码的几点说明： （1）BFS求迷宫最短路径，记录每个节点的前驱节点使用了mark标记。

可见，三种方法中mark标记可以根据实际需求灵活为其赋予意义。

（2）特殊的，起始节点的前驱设置为其本身。

小结告诫。

看着别人的代码去理解问题是如何求解的，对于求解算法题来说，这种方法是错误的。

正确的步骤是看别人的思路，理解如何求解后，给出自己的实现，才能够真正的深刻的掌握该题的求解。

经过自己思考的才能真正成为自己的东西。

不然的话，看着别人的代码痛苦不说，而且每个人的实现在很多细节都不相同，即是花了很长时间，暂时弄明白了，我想过不了多久就会忘记。

这样，得不偿失啊！参考文献[1]http://blog.csdn.net/a1259109679/article/details/48084951 [2]http://blog.csdn.net/bone_ace/article/details/41283585本文参与腾讯云自媒体分享计划，欢迎正在阅读的你也加入，一起分享。

展开阅读全文其他举报点赞2分享登录后参与评论动画演示广度优先算法寻找最短路径上一节，我们刚刚介绍了使用深度优先算法(DFS)解决迷宫问题，这一节我们来介绍广度优先算法(BFS)。

BFS算法与DFS十分相似，唯一的区别就是DFS...用户2870857深度优先搜索遍历与广度优先搜索遍历 1、图的遍历     和树的遍历类似，图的遍历也是从某个顶点出发，沿着某条搜索路径对图中每个顶点各做一次且仅做一次访问。

它是许多图的算法的基础。

    ...阳光岛主迷宫算法（DFS）1.如果采用堆栈进行迷宫探测，则称之为深度优先搜索（DFS），它和递归的探测思路是基本一致的，可以看成是递归方式的非递归版本；大忽悠爱学习浅析迷宫搜索类的双向bfs问题(附例题解析) 然而，当数据达到一定程度，我们使用简单的方法肯定会爆炸的，各种TLE(超时)，不分析原因还会一直提交一直TLE。

就可能需要一些特殊的巧妙方法处理，比如各种剪枝...bigsai深度优先搜索以上递归实现斐波那契实际上就是按照深度优先的方式进行搜索。

也就是“一条路走到黑”。

注意：这里的搜索指的是一种穷举方式，把可行的方案都列举出来，不断尝试，直到...可爱见见【手撕算法】opencv实现走迷宫算法本文利用opencv实现了深度优先搜索DFS和广度优先搜索BFS两个算法来走迷宫，迷宫也是用opencv+鼠标画的。

threeQingLeetCode529.扫雷游戏（广度优先搜索BFS/深度优先搜索DFS）给定一个代表游戏板的二维字符矩阵。

‘M’代表一个未挖出的地雷， ‘E’代表一个未挖出的空方块， ‘B’代表没有相邻（上，下，左，右，和所有4个对角...Michael阿明迷宫问题(BFS问题)-POJ3984本题是新加入我们的大虾Gabriel童鞋写的，他是一个刚入大学的大一新生，孺子如虎也，赞！ACM算法日常算法：队列与广度优先搜索（迷宫问题）队列也是一组元素的集合，也提供两种基本操作：Enqueue（入队）将元素添加到队尾，Dequeue（出队）从队头取出元素并返回。

就像排队买票一样，先来先服务，先...s1mba算法和数据结构:十二无向图相关算法基础从这篇文章开始介绍图相关的算法，这也是Algorithms在线课程第二部分的第一次课程笔记。

yaphetsfang算法浅谈——走迷宫问题与广度优先搜索我们都知道，工业上的很多问题经过抽象和建模之后，本质还是数学问题。

而说到数学问题就离不开方程，在数学上我们可以用各种推算、公式，但是有没有想过在计算机领域我们如...TechFlow-承志算法：堆栈与深度优先搜索（迷宫问题）堆栈的访问规则被限制为Push和Pop两种操作，Push（入栈或压栈）向栈顶添加元素，Pop（出栈或弹出）则取出当前栈顶的元素，也就是说，只能访问栈顶元素而不能...s1mba人工智能搜索策略（上）  广度优先搜索： 从初始节点S0开始逐层向下扩展，在第n层节点还没有全部搜索完之前，不进入第n+1层节点的搜索。

Open表中的节点总是按进入的先后排序，先进...racaljk10分钟教你用python动画演示深度优先算法搜寻逃出迷宫的路径寻找起始节点与目标节点之间路径的算法，常用于搜索逃出迷宫的路径。

主要思想是，从入口开始，依次搜寻周围可能的节点坐标，但不会重复经过同一个节点，且不能通过障碍节点...短短的路走走停停DFS与BFS为了方便读者查看简洁的DFS和BFS逻辑，这里把树的基本结构统一抽取出来且不讨论树的实现晚上没宵夜搜索专题2|3D地宫寻路POJ-2251上一篇我们做了一道棋子摆放的题目，采用的是DFS算法，本篇是一篇BFS算法，在刚开始学习搜索算法的时候，会觉得DFS和BFS算法非常相似，因为都是搜索然后得到结...ACM算法日常DataStructuresandAlgorithmsBasics（012）：Graph用户5473628图文详解DFS和BFS深度优先遍历（DepthFirstSearch,简称DFS）与广度优先遍历（BreathFirstSearch）是图论中两种非常重要的算法，生产上...kunge图图由两个部分组成，一是点node，二是边edge。

图的表示方法由邻接表法和邻接矩阵法。

当然还有其他的方式。

如下所示，有一无向图，其邻接表和邻接矩阵示意图为：用户1145562更多文章Dabelv腾讯后台开发工程师腾讯·后台开发工程师(已认证)关注专栏文章614阅读量534.4K获赞1.3K作者排名245腾讯云原生专题云原生技术干货，业务实践落地。

一键订阅《云荐大咖》专栏获取官方推荐精品内容，学技术不迷路！立即查看腾讯云自媒体分享计划入驻云加社区，共享百万资源包。

立即入驻目录1.问题简介2.求解方法3.方法详解与具体实现3.1深度优先搜索（DFS）加回溯求解第一条可行路径3.2改进深度优先搜索（DFS）加回溯求解最短路径3.3广度优先搜索（BFS）求解迷宫的最短路径小结参考文献社区专栏文章阅读清单互动问答技术沙龙技术快讯团队主页开发者手册腾讯云TI平台活动原创分享计划自媒体分享计划邀请作者入驻自荐上首页在线直播生态合作计划资源技术周刊社区标签开发者实验室关于视频介绍社区规范免责声明联系我们友情链接归档问题归档专栏文章归档快讯文章归档关键词归档开发者手册归档开发者手册Section归档云+社区扫码关注云+社区领取腾讯云代金券热门产品域名注册云服务器区块链服务消息队列网络加速云数据库域名解析云存储视频直播热门推荐人脸识别腾讯会议企业云CDN加速视频通话图像分析MySQL数据库SSL证书语音识别更多推荐数据安全负载均衡短信文字识别云点播商标注册小程序开发网站监控数据迁移Copyright©2013-2022TencentCloud.AllRightsReserved.腾讯云版权所有京公网安备11010802017518粤B2-20090059-1扫描二维码扫码关注云+社区领取腾讯云代金券