自动走迷宫(2)–深度优先(非递归)算法

       上一期的‘左手法则’走迷宫我称之为‘感性方式’，局限性很大，而接下来的则是用算法来寻址的‘理性方式‘。这一期用深度优先（DFS）（非递归方式）来完成自动走迷宫。

       简单科普几个概念，官方解释dogedoge自己看吧，说一下我自己的理解：首先是两个基本算法深度优先遍历(DFS)和广度优先遍历(BFS)，对比着比较好理解，深度优先就是‘一个猛子扎到底’，忽略层级的，而广度优先则是按层级一级一级遍历的。还有要用到的两个数据结构：栈与队列，都是存放数据的容器，只是取数据的方式不同；栈为‘后进先出’，要从末尾取数据；队列则是‘先进先出’，要从头部取数据。

       言归正传，用深度优先走迷宫就遍历生成的地图迷宫列表，寻找一条从起点到终点全是‘0’的路线。伪代码如下：

（1）从迷宫起点节点V开始访问

（2）访问这个节点V，标记为可行的路径；

（3）从v的未被访问的非”墙”邻接点中选取一个顶点w，重复第二步。如果v没有未访问的非”墙”邻接点，把这个节点的可行路径标记移除，回溯至上一节点；

（4）重复上述第（2）、（3）步，直至遍历到迷宫的出口节点。

 

       逻辑与生成迷宫是一样的，非常简单，只是图像化语言的特点，代码可能会很长，其他语言的话就简洁多了，废话不说了，直接上图！~

 

    先初始化，设置好起点和终点位置。

 

将起点压栈，然后进入循环：

        取栈顶元素设置为当前单元，标记为已访问；

        如果当前单元周围有‘是路’并且‘未访问’的邻接单元(待处理列表项目数>0)，选取第一个，将其压栈。

        否则将当前单元出栈。

 

注意：返回当前单元周围情况与生成迷宫方法类似，就是寻找有‘是路’并且‘未访问’的单元，并把它们放入待处理列表，基于迷宫寻址方式，加入顺序是“右-下-左-上”。

 

       执行上面的方法后，栈内留下的元素就是从起点到终点各个能够联通的节点，将它们连线就大功告成了！~

 

转自公众号：
嘻嘻哈哈学编程