并查集原理
并查集,在一些有N个元素的集合应用问题中,我们通常是在开始时让每个元素构成一个单元素的集合,然后按一定顺序将属于同一组的元素所在的集合合并,其间要反复查找一个元素在哪个集合中
并查集是一种树型的数据结构,用于处理一些不相交集合的合并及查询问题,常常在使用中以森林来表示
适合于描述这类问题的抽象数据类型称为并查集(union-findset)
小例子-编号和人
如果我们想让编号和人构成关系, 即可以通过编号找到对应的人,也可以通过人找到对应的编号怎么做?
template<classT>
classUnionFindSet
{
public:
UnionFindSet(constT*a, size_tn)
{
for (inti=0; i<n; i++)
{
_a.push_back(a[i]);
_indexMap[a[i]] =i;
}
}
private:
vector<T>_a; //编号找人 下标对应的就是人名
map<T, int>_indexMap;//人找编号 key:人名 value:编号
};
#include"UnionFind.h"
intmain()
{
stringa[] = { "张三","李四","王五" };
UnionFindSet<string>ufs(a, 3);
return0;
}
并查集的实现
#include
#include
classUnionFindSet
{
public:
UnionFindSet(size_tn);
size_tFindRoot(intx);
voidUnion(intx1, intx2);
boolInset(intx1,intx2);
size_tSetCount();
private:
std::vector<int>_set;
};
首先我们要知道如下规则:
- 数组的下标对应集合中元素的编号
- 数组中的值如果为负数,负号代表根,数字代表该集合中元素个数
- 数组中的值如果为非负数,代表该元素双亲在数组中的下标
例如:
基本结构
classUnionFindSet
{
private:
std::vector<int>_set;
};
构造函数
最初每个元素各自构成一个集合, 初始状态就是-1,表示size个集合
UnionFindSet(intsize)
:_set(size, -1)//size个元素都最初初始化为-1
{}
查找根节点
返回根节点所在下标
//如果_set[x]是负数,那么x就是某个集合的根
//如果_set[x]不是负数,那么x的父亲节点就是_set[x]值对应的位置
size_tFindRoot(intx)
{
while (_set[x] >=0)
{
x=_set[x];
}
//来到这,_set[x] <0, 此时x就是根节点
returnx;
}
路径压缩技巧
路径压缩实际上是在数据量太大的时候,访问一些数据可能在位于叶子位置,导致访问的效率不高
本质上我们查找的代表节点的时候,可以对该路径上的节点进行路径压缩
注意:最好不要用递归的时候进行路径压缩,因为路径深可能导致栈溢出
做法:
1)先找到当前路径节点的代表节点
2)然后从当前位置_set[x]开始的节点,沿途的节点的父亲位置都改为代表节点的位置
只需要根据下标关系往上迭代即可x节点的父亲位置就是_set[x]位置
注意:要提前保存x节点的父亲节点位置,因为更改当前位置的父亲节点, 会丢失以前的父亲节点
size_tFindRoot(intx)
{
introot=x;
while (_set[root] >=0)
{
root=_set[root];
}
//此时root就是x这条路径的头节点(代表节点)
//把沿途的节点的父亲都改为root
while (_set[x] >=0)
{
intparent=_set[x];//先保存x节点的父节点位置
_set[x] =root;//将x节点的父亲位置改为root位置
x=parent;//往上迭代
}
returnroot;
}
合并集合
这里选择合并到x2所在的集合合并到x1所在的集合
voidUnion(intx1, intx2)
{
//找到x1和x2的代表节点(根节点)
size_troot1=FindRoot(x1);
size_troot2=FindRoot(x2);
//两个节点不在一个集合才合并
//把root2合并到root1所在集合
if (root1!=root2)
{
_set[root1] +=_set[root2];//root2所在集合的元素累加到root1所在集合
_set[root2] =root1; //root2的父亲变为root1
}
}
如果我们希望是小集合合并到大集合呢? 即元素少的集合合并到元素多的集合
路径压缩技巧
两颗树合并的时候,节点少的数往节点多的树合并
目的：为了使节点层数增多的节点相对减少
做法:
1)判断哪颗树的节点更多, 让root1变为是较大的集合, root2往root1合并
如何判断呢? 因为root1和root2是根,_set[root]的值是负数,代表该集合的元素个数, _set[root]值越大,集合元素个数越少
//x1和x2合并 ->本质是代表节点(根节点)合并
voidUnion(intx1, intx2)
{
//找到x1和x2的代表节点(根节点)
size_troot1=FindRoot(x1);
size_troot2=FindRoot(x2);
//我们让root1的集合是大集合,小集合合并到大集合中
//因为root1和root2是根,所以_set[root]的值为负数,代表集合的元素个数,值越小,元素越多
if (_set[root1] >_set[root2]) //说明root2集合元素多
{
::swap(root1, root2);
}
//两个节点不在一个集合才合并
if (root1!=root2)
{
_set[root1] +=_set[root2];//root2所在集合的元素累加到root1所在集合
_set[root2] =root1; //root2的父亲变为root1
}
}
求集合个数
遍历_set,查看有多少元素是负数,就代表有多少个根节点, 即有多少个集合
size_tSetCount()
{
size_tcount=0;
for (autoe : _set)
{
if (e<0) count++;
}
returncount;
}
判断两个元素是否在同一个集合
只需要判断两个元素的代表节点的位置是否相同即可
boolInset(intx1,intx2)
{
returnFindRoot(x1) ==FindRoot(x2);
}
