自动走迷宫(2)--深度优先(非递归)算法
上一期的‘左手法则’走迷宫我称之为‘感性方式’，局限性很大，而接下来的则是用算法来寻址的‘理性方式‘。这一期用深度优先（DFS）（非递归方式）来完成自动走迷宫。
简单科普几个概念，官方解释dogedoge自己看吧，说一下我自己的理解：
首先是两个基本算法深度优先遍历(DFS)和广度优先遍历(BFS)，对比着比较好理解，深度优先就是‘一个猛子扎到底’，忽略层级的，而广度优先则是按层级一级一级遍历的。还有要用到的两个数据结构：栈与队列，都是存放数据的容器，只是取数据的方式不同；栈为‘后进先出’，要从末尾取数据；队列则是‘先进先出’，要从头部取数据。
言归正传，用深度优先走迷宫就
遍历生成的地图迷宫列表，寻找一条从起点到终点全是‘0’的路线
。伪代码如下：
（3）从v的未被访问的非"墙"邻接点中选取一个顶点w，重复第二步。
如果v没有未访问的非"墙"邻接点，把这个节点的可行路径标记移除，回溯
至上一节点；
（4）重复上述第（2）、（3）步，直至遍历到迷宫的出口节点。
逻辑与生成迷宫是一样的，非常简单，只是图像化语言的特点，代码可能会很长，其他语言的话就简洁多了，废话不说了，直接上图！~
如果当前单元周围有‘是路’并且‘未访问’的邻接单元(待处理列表项目数>0)，选取第一个，将其压栈。
注意：返回当前单元周围情况与生成迷宫方法类似，就是寻找有‘是路’并且‘未访问’的单元，并把它们放入待处理列表，基于迷宫寻址方式，加入顺序是“右-下-左-上”。
执行上面的方法后，栈内留下的元素就是从起点到终点各个能够联通的节点，将它们连线就大功告成了！~
————————————————
标签:
