Yukang's Page

迷宫生成算法–并查集

2010-07-20

好书好书


在看《数据结构与算法分析》这本书的时候看到后面的一个关于并查集的有趣应用,是个生成迷宫的算法,看起来非常有趣,所以就实现了一下。顺便把几种走迷宫的算法都整了 进去。八卦一下,这本书的作者是Mark Weiss,这牛写了几本数据结构和算法的书,各种语言版本(C,C++,Java),原来是师出名门啊,在他的主页上一看,原来是Robert Sedgewick 的学生。Sedgewick更是师出名门,在Princeton跟高纳德神牛读的博士,也写了N本算法和数据结构的书。这两人写的书都还不错,对于初学者和中等水平来说很好,覆盖了一般的数据结构和算法,同时带有一定的理论分析还有特定的语言实现。


并查集



可能一般的大学教材上面没有说这个数据结构,这是个很有趣的东西。《算法导论》上面用这个来作为均摊分析的例子吧。在ACM/ICPC中这个数据结构经常出现,有可能是一个小题 (难点的就是要维护节点之间关系的那种),或者是有的图论算法中实现要用,比如实现Kruskar算法求最小生成树。
并查集本身比较简单,主要是用来操作元素集合,支持的操作有:





  1. UnionSets(int root1,int root2),用来合并两个根节点。

  2. FindSet(int x) ,用来查找x所属的根节点。 一并一查,所以叫作并查集。实现时候可以通过按秩合并(union by rank),和路径压缩(path compression)来增加效率,可以获得几乎与总操作数m成线性关系的运行时间。

int rank[MAXSIZE];    // 节点高度的上界
int parent[MAXSIZE]; // 根节点
void Init(void){
memset(rank, 0, sizeof(rank));
for(int i=0; i < MAXSIZE; ++i )
parent[i] = i;
}

int FindSet(int x){// 查找+递归的路径压缩
if( x != parent[x] )
parent[x] = FindSet(parent[x]);
return parent[x];
}

void UnionSet(int root1, int root2){
int x = FindSet(root1), y = FindSet(root2);
if( x == y ) return ;
if( rank[x] > rank[y] ) parent[y] = x;
else{
parent[x] = y;
if( rank[x] == rank[y] ) ++rank[y];
}
}

迷宫的实现


上面那本书上的习题上给了提示,比如首先所有的墙都没有去掉,那么是一个一个的方格,每一个方格为并查集合的一个元素,已经连通的元素是在并查集的一个集合中,有相同的根节点。 随机的选择一个墙,在并查集中查询这两个元素是否已经连通,如果已经连通则另选一个墙,如果不连通,union两个节点的根节点,这样操作以后这两个方格已经连通。继续上面的操作, 直到入口和出口连通位置,那么这就形成了一个只有一条合法路径的迷宫,称为单迷宫。如下图所示。

左上角起点 右下角终点





使用微信打赏

若你觉得我的文章对你有帮助,欢迎点击上方按钮对我打赏

扫描二维码,分享此文章