深度优先与广度优先搜索求解（以迷宫问题为例）

一、迷宫问题介绍

给定一个迷宫（以5×5为例），指明起点和终点，找出从起点出发到终点的有效可行路径，就是迷宫问题（maze problem）。

迷宫可以以二维数组来存储表示。0表示通路，1表示障碍。注意这里规定移动可以从上、下、左、右四方方向移动。坐标以行和列表示，均从0开始，给定起点（0,0）和终点（4,4），找出一条可行的线路（如果有，没有返回错误信息）。

二、求解思路

因为迷宫问题很难直接通过数学方法求解，故遍历是解决此问题的最有效方式。由数据结构的相关知识知，迷宫问题的求解可以抽象为连通图的遍历，故深度优先搜索和广度优先搜索是解决此问题的两种有效方法。

1、深度优先搜索（DFS）

其优点：无需记录前驱结点确认后退情况。

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

2、广度优先搜索（BFS）

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

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

三、数据结构知识补充（知晓请跳过此部分）

以下资料来自维基百科（中文版）对应词条，略做改动。

队列，即queue，是先进先出（FIFO, First-In-First-Out）的线性表。在具体应用中通常用链表或者数组来实现（在Java中可以直接将某一链表赋值给队列，我们稍后可能会在BFS算法中用到）。队列只允许在后端（称为rear）进行插入操作，在前端（称为front）进行删除操作。

堆栈，即stack，又称为栈或堆叠，是一种特殊的串列形式的数据结构（用一维数组或连结串列的形式来完成），其特殊之处在于只能允许在链接串列或阵列的一端（称为堆叠顶端指标，top）进行加入数据（push）和输出数据（pop）的运算；由于堆叠数据结构只允许在一端进行操作，因而按照后进先出（LIFO, Last In First Out）的原理运作。

四、算法解释+代码实现

一、深度优先搜索（DFS）[代码由 韩宝坤 提供，感谢！]

韩宝坤先(da)生(lao)暂未给出解释说明，请大家根据代码自行理解……



二、广度优先算法（BFS）

我们从起点开始，将每一个坐标（基于Point类实例化的对象，同时记录当前位置和前步位置）排入队列中，然后在队列非空的情况下取出最上方的坐标对象（即最后一步的点）并压入堆栈并标记此位置被访问过，然后一次探索当前位置附近的四个位置以判断下一步的行走路线，若发现可行则建立新节点记录，同时排入队列，反之此路不通则放弃该路线，继续从队列中取出上一步的位置并继续探索，依次递归，直到进入迷宫出口。

出口位置通过最后一次的坐标（堆栈最顶端）的步数+1输出总步数，并从当前点坐标开始，依次取出堆栈中的元素，从而实现逆向输出此条可行路线，同时方法返回0，反之返回-1。主程序根据方法的返回值进行判断，若不为0则输出无可行路线。

以下为参考代码实现：