快速业务通道

并查集UFSet类

作者 佚名技术 来源 程序设计 浏览 发布时间 2012-05-23

/*

Name: 并查集UFSet类

Copyright: 始发于goal00001111的专栏;允许自由转载,但必须注明作者和出处

Author: goal00001111

Date: 23-12-08 15:21

Description: 实现了普通的查找和合并的算法,也实现了压缩路径和按大小求并高效 算法,并对两者进行了测试比较。

有关算法的分析讨论详见拙作《一种简单而有趣的数据结构--并查集》:

http://blog.csdn.net/goal00001111/archive/2008/12/24/3595844.aspx

*/

#include <iostream>
#include <time.h>
using namespace std;
const int MAX = 50000; //集合的最大成员数量
class UFSet{ //并查集类
public:
UFSet(int s = MAX); //构造函数
UFSet(const UFSet & obj); //拷贝构造函数
~UFSet() //析构函数
{
delete []father;
}
UFSet & operator = (const UFSet & obj); //赋值函数
int FindFather(int pos); //寻找序号pos的族长大人
bool Unite(int posI, int posJ);//将成员posI和posJ合并到同一个家族
int FindFatherAndReducePath(int pos); //查找族长并压缩路径
bool UnionBySize (int posI, int posJ); //按大小求并
bool SameFamily(int posI, int posJ); //判断成员posI和posJ是否属于同一家族
void PrintUFSet();
private:
int *father; //并查集成员数组,存放各元素的父亲结点
int size; //并查集成员数量
};
UFSet::UFSet(int s) : size(s) //构造函数
{
father = new int[size + 1];
for (int i=0; i<=size; i++) //所有的数组元素值均初始化为-1
father[i] = -1;
}
UFSet::UFSet(const UFSet & obj) //拷贝构造函数
{
size = obj.size;
father = new int[size + 1];
for (int i=0; i<=size; i++)
father[i] = obj.father[i];
}
UFSet & UFSet::operator = (const UFSet & obj) //赋值函数
{
if (this == &obj) //检查自赋值
return *this;
delete []father; //释放原有的内存资源
size = obj.size; //分配新的内存资源,并复制内容
father = new int[size + 1];
for (int i=0; i<=size; i++)
father[i] = obj.father[i];
return *this; //返回本对象的引用
}
int UFSet::FindFather(int pos)//寻找序号pos的族长大人。若pos本身是族长,则返回 自身
{
if (father[pos] < 0)
return pos;
return FindFather(father[pos]);
}
bool UFSet::Unite(int posI, int posJ)//将成员posI和posJ合并到同一个家族
{
//首先各自去寻找自己的族长
int fI = FindFather(posI);
int fJ = FindFather(posJ);
if (fI == fJ) //如果是同一个族长门下,不必合并,即合并失败
return false;
else
father[fJ] = fI; //否则fI当族长:谁让posI站在posJ的前面呢!
return true;
}
int UFSet::FindFatherAndReducePath(int pos)//查找族长并压缩路径
{
if (father[pos] < 0)
return pos;
//若自己不是族长,则找到族长后,将所途经的结点均指向族长
return father[pos] = FindFatherAndReducePath(father[pos]);
}
bool UFSet::UnionBySize(int posI, int posJ)//按大小求并
{
//首先各自去寻找自己的族长
int fI = FindFatherAndReducePath(posI);
int fJ = FindFatherAndReducePath(posJ);
if (fI == fJ) //如果是同一个族长门下,不必合并,即合并失败
return false;
else if (father[fI] < father[fJ])
{//如果族长fI的实力比fJ强,即|fI|>|fJ|,则fI当族长,并修改father[fI]和 father[fJ]
father[fI] += father[fJ];
father[fJ] = fI;
}
else //否则fJ当族长
{
father[fJ] += father[fI];
father[fI] = fJ;
}
return true;
}
bool UFSet::SameFamily(int posI, int posJ)//判断成员posI和posJ是否属于同一家族
{
retu

凌众科技专业提供服务器租用、服务器托管、企业邮局、虚拟主机等服务,公司网站:http://www.lingzhong.cn 为了给广大客户了解更多的技术信息,本技术文章收集来源于网络,凌众科技尊重文章作者的版权,如果有涉及你的版权有必要删除你的文章,请和我们联系。以上信息与文章正文是不可分割的一部分,如果您要转载本文章,请保留以上信息,谢谢!

分享到: 更多

Copyright ©1999-2011 厦门凌众科技有限公司 厦门优通互联科技开发有限公司 All rights reserved

地址(ADD):厦门软件园二期望海路63号701E(东南融通旁) 邮编(ZIP):361008

电话:0592-5908028 传真:0592-5908039 咨询信箱:web@lingzhong.cn 咨询OICQ:173723134

《中华人民共和国增值电信业务经营许可证》闽B2-20100024  ICP备案:闽ICP备05037997号