首页 > 不相交集类以及应用迷宫生成

不相交集类以及应用迷宫生成

简单介绍：

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

因此主要是两个问题：

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）调用时，修改递归找到的结点直接指向等价类的代表结点，使得路径上的结点移近根结点，这样下次调用时就很快了。

正如书上所说：

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

clip_image002

clip_image004

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

效率什么的没有考虑。

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

/********************************************************************************
 **
 **       Filename:  DisjSets.h
 **
 **    Description:  
 **
 **        Version:  1.0
 **        Created:  2011年12月06日 11时43分46秒
 **       Revision:  none
 **       Compiler:  gcc
 **
 **         Author:  zhy (), [email protected]
 **        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<int> s;
};
#endif//DISJSETS_H



/********************************************************************************
 **
 **       Filename:  DisjSets.cpp
 **
 **    Description:  
 **
 **        Version:  1.0
 **        Created:  2011年12月06日 11时45分09秒
 **       Revision:  none
 **       Compiler:  gcc
 **
 **         Author:  zhy (), [email protected]
 **        Company:  
 **
 *********************************************************************************/
#include "DisjSets.h"DisjSets::DisjSets(int numElements) : s(numElements)
{for ( int i=0; iint DisjSets::find(int x)
{//cout << "DisjSets::find x= " << x << "	s[x] = " << s[x] << endl;if (s[x]<0)return x;else {s[x] = find(s[x]);return s[x];}
}void DisjSets::unionSets(int root1, int root2)
{if (s[root1]>s[root2]) {s[root1] = root2;} else {if (s[root1]==s[root2])s[root1]--;s[root2] = root1;}
}



/********************************************************************************
 **
 **       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 (), [email protected]
 **        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; ifor ( int j=0; jdelete mRoom[i][j];for ( int i=0; idelete [] mRoom[i];delete [] mRoom;}void print();private:bool isConnected(Room *room1, Room *room2) {return (mData->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 (), [email protected]
 **        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; inew Room*[column];for ( int i=0; ifor ( int j=0; jnew Room(i,j);mRoom[0][0]->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
",__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
",__FUNCTION__);//printf("(%d,%d)-->(%d,%d)
",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
",__FUNCTION__);for ( int i=0; ifor ( int j=0; j"%2d ",mData->find(mRows*i+j));printf("
");}for (int j=0; j"__");printf("
");for ( int i=0; ifor ( int j=0; jchar s[3] = "  ";if (((j-1<0) && i!=0) || mRoom[i][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("
");}
}


参考资料：

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



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

更多相关：

  • java 读取excel_Java12POI操作Excel

            Apache POI是一个开源的利用Java读写Excel，WORD等微软OLE2组件文档的项目。        我的需求是对Excel的数据进行导入或将数据以Excel的形式导出。先上简单的测试代码：package com.xing.studyTest.poi;import java.io.FileInputSt...

  • C++ 生成随机数

    要取得[a,b)的随机整数，使用(rand() % (b-a))+ a; 要取得[a,b]的随机整数，使用(rand() % (b-a+1))+ a; 要取得(a,b]的随机整数，使用(rand() % (b-a))+ a + 1; 通用公式:a + rand() % n；其中的a是起始值，n是整数的范围。 要取得a到b之间的...

  • 基于C++的本征图像分解(Intrinsic Image Decomposition)

    利用本征图像分解(Intrinsic Image Decomposition)算法，将图像分解为shading(illumination) image 和 reflectance(albedo) image，计算图像的reflectance image。 Reflectance Image 是指在变化的光照条件下能够维持不变的图像部分...

  • 剑指offer：面试题39. 数组中出现次数超过一半的数字

    题目：面试题39. 数组中出现次数超过一半的数字 数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。 你可以假设数组是非空的，并且给定的数组总是存在多数元素。 示例 1: 输入: [1, 2, 3, 2, 2, 2, 5, 4, 2] 输出: 2 限制： 1 <= 数组长度 <= 50000 解题： cl...

  • 剑指offer：面试题33. 二叉搜索树的后序遍历序列

    题目：二叉搜索树的后序遍历序列 输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历结果。如果是则返回 true，否则返回 false。假设输入的数组的任意两个数字都互不相同。 参考以下这颗二叉搜索树：      5     /    2   6   /  1   3示例 1： 输入: [1,6,3,2,5] 输出...

  • linux命令find命令详解

    find 查找文件 find 哪里 什么类型 什么名字 -maxdepth 最大的深度 查找目录的最大深度    find -maxdepth 1 -type d -type 找什么类型的 f file 文件 d directory 目录 -name 什么名字 -mtime 根据修改时间找出对应的文件   +7 7天前  -7...

©2024 11GX.COM