本文主要是介绍深度优先遍历之迷宫生成算法，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
1、图的深度优先遍历简介
例如，要遍历上面这个图
采取深度优先算法(从1开始)
准备一个Stack s，预定义三种状态：A未被访问 B正准备访问 C已经访问
一、访问1，把它标记为已经访问，然后将于它相邻的并且标记为未被访问的点压入s 中并标记为正准备访问
此时系统状态：
已经被访问的点：1
还没有被访问的点：3 4 6 7 8 9 10
正准备访问的点：2 5 (存放在Stack之中)
二、从Stack中拿出第一个元素 2，标记为已经访问，然后将于它相邻的并且标记为未被访问的点压入s 中并标记为正准备访问，如图：
此时系统状态：
已经被访问的点：1 2
还没有被访问的点： 4 6 7 8 9 10
正准备访问的点：3 5 (存放在Stack之中)
三、从Stack中拿出第一个元素 3，标记为已经访问，然后将于它相邻的并且标记为未被访问的点压入s 中并标记为正准备访问，如图：
此时系统状态：
已经被访问的点：1 2 3 4
还没有被访问的点：8 9 10
正准备访问的点：7 6 5 (存放在Stack之中)
依此类推，重复上面的动作，直到Stack为空，即所有的点都被访问。
最后可能的遍历情况，如图：
2、深度优先遍历之迷宫生成算法
那么，这样该如何生成迷宫呢？
不知大家注意到了没有，这种算法每一个步骤都要执行一个操作，把刚刚访问过的点的相邻的并且没有标记为被访问过的点压入Stack s中，然后下一步访问的就是Stack中的第一个元素。那么，当一个点有多个相邻点的话，该按什么顺序压入呢？随机。这就是随机生成迷宫的核心所在！
现在我们换个角度看待问题。
例如需要生成一个5 * 5的迷宫。坐标为(1,1) (3,1) (1,3) (3,3)的①、②、③、④分别代表节点，它们肯定可让人通过，然后，如果(2,1)设置成可通过，就代表①?②可通过，结合图的遍历算法，我们看到，当我们从①访问到②时，就把(2,1)设置为可通过，就相当开辟了一条道路，等到遍历结束，迷宫就生成了。
上图中的①②③④，我们可看为一个2 * 2的矩阵，如图：
关键是在什么时候“开辟这条道路”。以上节中图的深度优先遍历简介为例子。假设依次访问到的点是：1 2 3 4 7 10 9 8 6 5
当刚刚访问到 9 时，会把8 6 压入Stack中，所以应该开通 9 到 8和6的道路，这样就可自动生成迷宫了。
3、迷宫路径的唯一性
这个算法，大家应该很清楚地看到，从起点到终点的路是唯一的（可以任选两点作为起点和终点）
4、算法的缺点
算法只能生成一个m * n的迷宫，其中m、n都是奇数。
这篇关于深度优先遍历之迷宫生成算法的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
