矩阵迷宫生成算法

脑残的数据结构课设要做个什么脑残的非递归迷宫问题求解。最脑残的是还让自己去生成一个迷宫。于是有了这篇文章。

言归正传。先介绍一个神奇的数据结构叫“并茶几” 哦不,“并查集”。并查集是一中用于判断元素是否属于同一集合的数据结构,主要的操作有查找和合并。并查集实际上是一个森林,每一个集合是一棵树。

在并查集中,默认每个元素的父元素指向自己,在执行合并操作的时候只需要将自己的父元素指向要合并的节点,即可完成合并。在执行查找的时候,只需要一直寻找父元素,直到父元素指向父元素本身。

但是当合并次数增多以后,可能会出现树的深度过大,导致每次回溯父节点耗时过长。这里有一种路径压缩的办法。在执行find的时候,将每个节点的父节点都改为最远处的父节点。在递归执行查找的时候只需要很小的改动即可。

还有一种按秩合并的算法可以优化并查集。但是远没有路径压缩简单易懂,在小规模数据时无需使用。

下面提供了一个简单封装过的并查集类。

说完了并查集就该让我们谈谈怎么去生成迷宫了。

迷宫实质上就是从原点到重点的一科生成树,生成树中的所有节点必属于同一个集合。于是借助并查集和随机数构造迷宫。

在生成迷宫时,我们随机选择一堵墙,并把墙打通,隔开的两个格子在并查集中合并。直到原点和终点在同一个集合中。

迷宫

以上就是用这种方法生成的迷宫矩阵。原点为(0,0),终点为(15,15)。迷宫通路较为曲折,下面是用深搜获得的解。

迷宫,解

 

这个生成算法有个缺点,因为相邻的两个点之间必有墙,所以只能生成奇数乘奇数的矩阵。如果有能生成偶数矩阵的算法,欢迎在下面留言讨论。

矩阵迷宫生成算法》有3个想法

发表评论

电子邮件地址不会被公开。 必填项已用*标注