简单介绍：

考虑一个迷宫的生成，一个简单算法就是从各处的墙壁开始（除入口和出口之外）。此时，不断地随机选择一面墙，如果被该墙分割的单元彼此不联通，那么就把这面墙拆掉。重复这个过程直到开始单元和终止单元联通，那么就得到一个迷宫。实际上不断的拆掉墙壁直到每个单元都可以从其他单元到达更好（这会使迷宫产生更多误导的路径）。

因此主要是两个问题：

1. 拆掉墙如果两个单元不连通。

2. 保留墙如果两个单元已经联通。

这里用于判断不同单元是否在同一集合的数据结构即为不相交集类。

基本知识：

即我们要建立多个等价类，联通的元素放在同一个等价类里面。

对应的，需要两个操作：

1. 将两个元素放到一个等价类里的话，采用union操作。

2. 查找某个元素在哪个等价类里，采用find操作。根据find的返回值可以判断两个元素是否在一个等价类里。

可以用数组来记录，程序里我使用的是vector（仿照书里的）。

举个例子看可能比较清楚：

假设元素ID刚开始为 0 1 2 3 4 5 6 7 8 9

建立相同大小的数组s，数组初始化值均为-1。

最直观的处理，比如union(4,5)即使s[5] = 4。（约定union(x,y)使得s[y]=x，效果是相同的）。

find(4)会直接返回4本身，因为s[4]<0。

而find(5)则递归调用，实际上为:find(5) = find(s[5]) = 4，因此判断出4，5属于同一个等价类（我觉得可以理解为4这个结点即为等价类的代表）。

find最坏情形运行时间为O（N），因为对N个元素，有可能建立一个深度为N-1的树。

因此对union和find操作都进行了改进。

为了控制树的深度，可以重写union的方式，比如unionBySize,unionByHeight，书上都介绍，这里就不说了。此时find运行时间为O(N)。

另外对于find巧妙的改进是路径压缩，即当find（x）调用时，修改递归找到的结点直接指向等价类的代表结点，使得路径上的结点移近根结点，这样下次调用时就很快了。

正如书上所说：

这种数据结构实现起来很简单，每个例程只需要几行代码，而且可以使用一个简单的数组。

可以看到迷宫差别很大，我只是使得入口出口两个单元连通起来即结束循环。

效率什么的没有考虑。

所有的代码：数据集合类，迷宫生成类

/******************************************************************************** ** **       Filename:  DisjSets.h ** **    Description:   ** **        Version:  1.0 **        Created:  2011年12月06日 11时43分46秒 **       Revision:  none **       Compiler:  gcc ** **         Author:  zhy (), izualzhy@163.com **        Company:   ** *********************************************************************************/#ifndef DISJSETS_H#define DISJSETS_H#include 
     
      #include 
      
       using namespace std;class DisjSets {public:    explicit DisjSets(int numElements);    int find(int x);    void unionSets(int root1, int root2);private:    vector
       
         s;};#endif//DISJSETS_H
       
      
     
/******************************************************************************** ** **       Filename:  DisjSets.cpp ** **    Description:   ** **        Version:  1.0 **        Created:  2011年12月06日 11时45分09秒 **       Revision:  none **       Compiler:  gcc ** **         Author:  zhy (), izualzhy@163.com **        Company:   ** *********************************************************************************/#include "DisjSets.h"DisjSets::DisjSets(int numElements) : s(numElements){    for ( int i=0; i
/******************************************************************************** ** **       Filename:  MazeDataGenerator.h ** **    Description:  generator the data of maze ** **        Version:  1.0 **        Created:  2011年12月06日 14时49分09秒 **       Revision:  none **       Compiler:  gcc ** **         Author:  zhy (), izualzhy@163.com **        Company:   ** *********************************************************************************/#ifndef MAZEDATAGENERATOR_H#define MAZEDATAGENERATOR_H#include 
     
      #include "DisjSets.h"class Room{public:    Room(int row, int col) :        i(row) ,        j(col)    {        for ( int i=0; i<4; ++i)            wall[i] = true;    }    int i;    int j;    bool wall[4];    bool operator==(const Room &room2)    {        return ((this->i)==(room2.i) && (this->j==room2.j));    }};class MazeDataGenerator {public:    enum Direction{        NORTH,        EAST,        SOUTH,        WEST    };    MazeDataGenerator(int row, int column);    ~MazeDataGenerator()    {        delete mData;        mData = NULL;        for ( int i=0; i
      
       find(room1->i*mColumns+room1->j)==mData->find(room2->i*mColumns+room2->j));    }    void initRoad();    bool connectTworoom(Room *room1, Room *room2, Direction d);private:    DisjSets *mData;    Room ***mRoom;    int mColumns;    int mRows;};#endif//MAZEDATAGENERATOR_H
      
     
/******************************************************************************** ** **       Filename:  MazeDataGenerator.cpp ** **    Description:   ** **        Version:  1.0 **        Created:  2011年12月06日 14时51分42秒 **       Revision:  none **       Compiler:  gcc ** **         Author:  zhy (), izualzhy@163.com **        Company:   ** *********************************************************************************/#include 
     
      #include 
      
       #include 
       
        #include "MazeDataGenerator.h"MazeDataGenerator::MazeDataGenerator(int row, int column) :    mRows(row) ,    mColumns(column) {    srand(time(NULL));    mData = new DisjSets(row*column);    mRoom = new Room**[row];    for ( int i=0; i
        
         wall[NORTH] = mRoom[0][0]->wall[EAST] = false;    mRoom[mRows-1][mColumns-1]->wall[SOUTH] = mRoom[0][0]->wall[WEST] = false;    initRoad();}void MazeDataGenerator::initRoad(){    printf("%s\n",__FUNCTION__);    Room *room = mRoom[0][0];    while (!isConnected(mRoom[0][0],mRoom[mRows-1][mColumns-1])) {        Direction side = (Direction)(rand()%4);        int i = room->i;        int j = room->j;        switch(side) {            case NORTH:                i = room->i-1;                break;            case SOUTH:                i = room->i+1;                break;            case EAST:                j = room->j-1;                break;            case WEST:                j = room->j+1;                break;        }        if (i<0 || i>=mRows || j<0 || j>=mColumns)            continue;        if (!isConnected(mRoom[room->i][room->j],mRoom[i][j]))            connectTworoom(mRoom[room->i][room->j],mRoom[i][j],side);        room = mRoom[i][j];        //print();    }}bool MazeDataGenerator::connectTworoom(Room *room1, Room *room2, Direction d){    //printf("%s\n",__FUNCTION__);    //printf("(%d,%d)-->(%d,%d)\n",room1.i,room1.j,room2.i,room2.j);    if (room1==room2)        return false;    int index1 = room1->i*mColumns+room1->j;    int index2 = room2->i*mColumns+room2->j;    int root1 = mData->find(index1);    int root2 = mData->find(index2);    if (root1==root2) return false;    mData->unionSets(root1,root2);    room1->wall[d] = false;    room2->wall[(d+2)%4] = false;    return true;}void MazeDataGenerator::print(){    printf("%s\n",__FUNCTION__);    for ( int i=0; i
         
          find(mRows*i+j));        printf("\n");    }   for (int j=0; j
          
           wall[1]) s[0]='|'; if ((i+1)>=mRows || mRoom[i][j]->wall[2]) s[1]='_'; printf("%s",s); if ((j+1)==mColumns && i!=mRows-1) printf("|"); } printf("\n"); }}

参考资料：

数据结构与算法分析—C++描述

转载自 http://www.cppblog.com/izualzhy/archive/2011/12/11/161913.html