文档介绍：嗯... 其实也没啥... 随便敲了一段程序..
先上效果图:
其实随机化 Kruskal 来搞迷宫程序也是很正常..
相比 DFS 这种危险的东西而言要好得多了..
/* ----------------------------------------------
就是求一个随机生成树的问题..
思路就是:
假如把每个空格看成一个点. 空格与空格之间的墙壁看成一条边.
那么初始的迷宫就是一个无向图 G = <V , E>
然后我要使得入口和出口要联通.
相当于去搞一个图G 的导出子图, 使得子图中的顶点 E 和顶点 S 是联通的.
有点算法功底的人应该想到对于DFS这种东西...实在是害怕栈溢出... 你有本事就改成非递归形式.. 但估计没人有本事. 还不如用生成树的思路做.
算法步骤:
1)随机选择 G 中的一条边 e ∈ E , 判断 e 连接的两个顶点是否在同一集盒,
如果不是, 将两个顶点所在集盒合并, 并且把墙擦掉;
反之, 进入 2)
2) E = E - {e} ; //从边集中去掉元素 e
3) 如果 E = Φ(空集) , 结束算法; 反之, 转到 1)
这其中的判断两个顶点在同一集盒以及将两顶点合并如果要高效率的操作的话.
仅仅用线性表是肯定会**的.. 这里用数据结构里常用的树来存储.
即所谓的 UFS(Union_Find_Set) 并查集.
这个数据结构我已经手写成了类, 放在了源代码中.
还有迷宫地图相关的操作函数以及变量全部放在了命名空间 Maze 中,不然冲突的太严重了.
另外: 命名空间 std 我并没有完全开放, 这也是给新手一种示范。告诉C++初学者,别为了偷懒就随便的全局"using namespace std;" , 大项目中的后果是很坑爹的....
(源代码整理后以图片形式贴出)
///////////// 这帖子在代码全部贴出前尽量别插楼(谢谢大家的配合) /////////////
8
8
最后附上使用的std
std::list
std::pair
std::cin
std::cout
std::endl