肥康

好书好书

在看《数据结构与算法分析》这本书的时候看到后面的一个关于并查集的有趣应用，是个生成迷宫的算法，看起来非常有趣，所以就实现了一下。顺便把几种走迷宫的算法都整了 进去。八卦一下，这本书的作者是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两个节点的根节点，这样操作以后这两个方格已经连通。继续上面的操作， 直到入口和出口连通位置，那么这就形成了一个只有一条合法路径的迷宫，称为单迷宫。如下图所示。

随机日志

• A Emacs func (0)
• A Complaint Free World (3)
• using automake (0)
• A*算法与K-shortest path问题 (3)
• C 单元测试 (0)
• Cflow 分析 (9)
• The Game of Life (0)
• 姓氏的消失 (3)
• 从豆瓣FM下载喜欢的音乐 (4)
• 乱想想 (1)

Tags: 并查集 迷宫

This entry was posted on 星期二, 七月 20th, 2010 at 1:47 下午 and is filed under Programming. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.