用图论解决迷宫地图问题

简单的介绍

3.2结合图论的迷宫生成算法

3.2.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为空，即所有的点都被访问

最后可能的遍历情况，如图：

3.2.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.2.3迷宫路径的唯一性

这个算法，大家应该很清楚地看到，从起点到终点的路是唯一的（可以任选两点作为起点和终点）

3.2.4算法的缺点

算法只能生成一个m * n的迷宫，其中m、n都是奇数。

本文来源：https://www.bwwdw.com/article/4ea1.html