程序员的喵

迷宫生成算法–并查集

2010-07-20

好书好书

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

并查集

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

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

  • 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 两个节点的根节点,这样操作以后这两个方格已经连通。继续上面的操作, 直到入口和出口连通位置,那么这就形成了一个只有一条合法路径的迷宫,称为单迷宫。如下图所示。

    左上角起点 右下角终点

    公号同步更新,欢迎关注👻