您现在的位置是:首页 >技术交流 >高阶数据结构 ——— 并查集网站首页技术交流
高阶数据结构 ——— 并查集
并查集
- 并查集是一种树型的数据结构,用于处理一些不相交集合的合并及查询问题。
- 并查集通常用森林来表示,森林中的每棵树表示一个集合,树中的结点对应一个元素。
说明一下: 虽然利用其他数据结构也能完成不相交集合的合并及查询,但在数据量极大的情况下,其耗费的时间和空间也是极大的。
并查集的原理
并查集的原理
以朋友圈为例,现在有10个人(从0开始编号),刚开始这10个人互不认识,所以各自属于一个集合。如下:
并查集会用一个数组来表示这10个人之间的关系,数组的下标对应就是这10个人的编号,刚开始时数组中的元素都初始化为-1。如下:
说明一下:
- 数组中某个位置的值为负数,表示该位置是树的根,这个负数的绝对值表示的这棵树(集合)中数据的个数,因为刚开始每个人各自属于一个集合,所以将数组中的位置都初始化为-1。
后来这10个人之间通过相互认识,最终形成了三个朋友圈。如下:
此时并查集数组中各个位置的值如下:
说明一下:
- 数组中某个位置的值为非负数,表示该位置不是树的根,这个非负数的值就是这个结点的父结点的编号。
后来4号和8号又通过某种机遇互相认识了,这时他们所在的两个集合就需要进行合并,最终就变成了两个朋友圈。如下:
需要注意的是,在根据两个元素合并两个集合时,需要先分别找到这两个元素所在集合的根结点,然后再将一个集合合并到另一个集合,并且合并后需要更新数组中根结点的值。
示意图如下:
合并集合找根结点的原因:
- 如果这两个元素所在集合的根结点相同,说明这两个元素本身就在同一个集合,无需合并。
- 合并集合后需要更新这两个集合的根结点的值。
而要判断两个元素是否在同一个集合,也就是判断这两个元素所在集合的根结点是否相同。
并查集的实现
并查集的实现
实现并查集时通常会实现如下接口:
- 初始化并查集。
- 查找元素所在的集合。
- 合并两个元素所在的集合。
- 获取并查集中集合的个数。
代码如下:
//并查集
class UnionFindSet {
public:
//构造函数
UnionFindSet(int n);
//查找元素所在的集合
int findRoot(int x);
//合并两个元素所在的集合
bool unionSet(int x1, int x2);
//获取并查集中集合的个数
int getNum();
private:
vector<int> _ufs; //维护各个结点之间的关系
};
并查集中的数组:
- 数组的下标依次对应每个元素的编号。
- 数组中元素值为负数,表示下标编号元素为根结点,负数的绝对值表示该集合中元素的个数。
- 数组中元素值为非负数,表示下标编号元素的父结点的编号。
并查集的初始化
并查集的初始化
并查集中会用一个数组来维护各个结点之间的关系,在初始化并查集时,根据元素的个数开辟数组空间,并将数组中的元素初始化为-1即可。
代码如下:
//构造函数
UnionFindSet(int n)
:_ufs(n, -1) //初始时各个元素自成一个集合
{}
查找元素所在的集合
查找元素所在的集合
查找元素所在的集合,本质就是查找元素所在集合的根结点。
查找逻辑如下:
- 如果元素对应下标位置存储的是负数,则说明该元素即为根结点,返回该元素即可。
- 如果元素对应下标位置存储的是非负数,则跳转到其父结点的位置继续查找根结点。
迭代方式实现如下:
//查找元素所在集合的根结点(迭代)
int findRoot(int x) {
int parent = x; //默认当前结点就是根结点
while (_ufs[parent] >= 0) { //当前结点值不是负数则继续向上找
parent = _ufs[parent];
}
return parent; //返回根结点
}
递归方式实现如下:
//查找元素所在集合的根结点(递归)
int findRoot(int x) {
return _ufs[x] < 0 ? x : findRoot(_ufs[x]);
}
合并两个元素所在的集合
合并两个元素所在的集合
合并逻辑如下:
- 分别找到两个元素所在集合的根结点。
- 如果这两个元素所在集合的根结点相同,则无需合并,如果这两个元素所在集合的根结点不同,则将小集合合并到大集合上。
- 将小集合根结点的值累加到大集合的根结点上,使得大集合根结点的值的绝对值等于两个集合中元素的总数。
- 将小集合根结点的值改为大集合根结点的编号,也就是让小集合的根结点作为大集合根结点的孩子,使得两个集合变为一个集合。
代码如下:
//合并两个元素所在的集合
bool unionSet(int x1, int x2) {
int parent1 = findRoot(x1), parent2 = findRoot(x2); //分别找到两个元素所在集合的根结点
if (parent1 == parent2) //两个结点已经位于同一集合
return false;
if (_ufs[parent1] > _ufs[parent2]) //让parent1标记大集合根结点,parent2标记小集合根结点
swap(parent1, parent2);
//将小集合合并到大集合上
_ufs[parent1] += _ufs[parent2]; //将小集合根结点的值累加到大集合的根结点上
_ufs[parent2] = parent1; //将小集合根结点的值改为大集合根结点的编号
return true;
}
说明一下:
- 当两个集合需要合并时,将小集合合并到大集合上,目的是为了让后续通过元素查找根结点时可以尽量少往上走一层,该操作不是必须的。
获取并查集中集合的个数
获取并查集中集合的个数
要获取并查集中集合的个数,本质就是统计数组中负值(根结点)的个数。
代码如下:
//获取并查集中集合的个数
int getNum() {
int count = 0; //统计根结点的个数
for (const int& val : _ufs) {
if (val < 0) //元素值为负数则为根结点
count++;
}
return count; //返回根结点的个数
}
并查集的路径压缩
并查集的路径压缩
当数据量很大的时候,并查集中树的层数可能会变得很高,这时在查找一个元素所在集合的根结点时就需要往上走很多层,这时可以考虑进行路径压缩。
- 路径压缩一般会在查找根结点时进行,当根据一个结点查找其根结点时,该路径上所有的结点都会被压缩,最终这些结点会直接被挂在根结点下,下次再根据这些结点查找根结点时就能快速找到根结点。
代码如下:
//查找元素所在集合的根结点(递归)
int findRoot(int x) {
int parent = x; //默认当前结点就是根结点
if (_ufs[x] >= 0) { //当前结点值不是负数则继续向上找
parent = findRoot(_ufs[x]); //找到根结点
_ufs[x] = parent; //将当前结点的父亲改为根结点(路径压缩)
}
return parent; //返回根结点
}
元素的编号问题
元素编号问题
上面在实现并查集时,默认元素的编号都是从0开始依次递增的,但用户所给的编号可能并不是从0开始的,也不是连续的,甚至可能不是数字。
这时可以以模板的方式来实现并查集:
- 在初始化并查集时,根据所给元素建立元素与数组下标之间的映射关系。
- 在查找元素所在集合的根结点时,先根据所给元素得到其对应的数组下标,然后再进行查找。
代码如下:
//并查集
template<class T>
class UnionFindSet {
public:
//构造函数
UnionFindSet(const vector<T>& v)
:_ufs(v.size(), -1) //初始时各个元素自成一个集合
{
//建立元素与数组下标之间的映射关系
for (int i = 0; i < v.size(); i++) {
_indexMap[v[i]] = i;
}
}
//查找元素所在集合的根结点(迭代)
int findRoot(const T& x) {
int parent = _indexMap[x]; //默认当前结点就是根结点
while (_ufs[parent] >= 0) { //当前结点值不是负数则继续向上找
parent = _ufs[parent];
}
return parent; //返回根结点
}
//合并两个元素所在的集合
bool unionSet(const T& x1, const T& x2) {
int parent1 = findRoot(x1), parent2 = findRoot(x2); //分别找到两个元素所在集合的根结点
if (parent1 == parent2) //两个结点已经位于同一集合
return false;
if (_ufs[parent1] > _ufs[parent2]) //让parent1标记大集合根结点,parent2标记小集合根结点
swap(parent1, parent2);
//将小集合合并到大集合上
_ufs[parent1] += _ufs[parent2]; //将小集合根结点的值累加到大集合的根结点上
_ufs[parent2] = parent1; //将小集合根结点的值改为大集合根结点的编号
return true;
}
//获取并查集中集合的个数
int getNum() {
int count = 0; //统计根结点的个数
for (const int& val : _ufs) {
if (val < 0) //元素值为负数则为根结点
count++;
}
return count; //返回根结点的个数
}
private:
vector<int> _ufs; //维护各个结点之间的关系
unordered_map<T, int> _indexMap; //建立元素与数组下标之间的映射关系
};
这样在使用并查集时就可以传入任意类型的元素了。如下:
int main() {
vector<string> v = { "张三", "李四", "王五", "赵六", "田七", "周八", "吴九" };
UnionFindSet<string> ufs(v);
cout << ufs.getNum() << endl; //7
ufs.unionSet("张三", "李四");
ufs.unionSet("王五", "赵六");
cout << ufs.getNum() << endl; //5
ufs.unionSet("张三", "赵六");
cout << ufs.getNum() << endl; //4
return 0;
}
并查集的题目
省份的数量
省份的数量
题目描述:
有
n
n
n 个城市,其中一些彼此相连,另一些没有相连,如果城市
a
a
a 与城市
b
b
b 直接相连,且城市
b
b
b 与城市
c
c
c 直接相连,那么城市
a
a
a 与城市
c
c
c 间接相连。省份是一组直接或间接相连的城市,组内不含其他没有相连的城市。
给你一个
n
×
n
n imes n
n×n 的矩阵,其中
i
s
C
o
n
n
e
c
t
e
d
[
i
]
[
j
]
=
1
isConnected[i][j]=1
isConnected[i][j]=1 表示第
i
i
i 个城市和第
j
j
j 个城市直接相连,而
i
s
C
o
n
n
e
c
t
e
d
[
i
]
[
j
]
=
0
isConnected[i][j]=0
isConnected[i][j]=0 表示二者不直接相连。返回矩阵中省份的数量。
解题步骤:
- 定义一个长度为 n n n 的数组充当并查集,并将数组中的元素初始化为-1,表示各个城市各自是一个省份。
- 根据所给矩阵,对并查集中的各个集合进行合并。
- 并查集中集合的个数即为省份的数量。
代码如下:
class Solution {
public:
int findCircleNum(vector<vector<int>>& isConnected) {
//1、初始化并查集
int n = isConnected.size();
vector<int> ufs(n, -1);
auto findRoot = [&ufs](int x)->int {
int parent = x;
while (ufs[parent] >= 0) {
parent = ufs[parent];
}
return parent;
};
//2、根据所给矩阵合并集合
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (isConnected[i][j] == 1) { //城市相连
int parent1 = findRoot(i), parent2 = findRoot(j);
if (parent1 != parent2) { //需要合并
ufs[parent2] = parent1;
}
}
}
}
//3、统计并查集中集合的个数
int count = 0;
for (const int& e : ufs) {
if (e < 0)
count++;
}
return count;
}
};
说明一下:
- 在使用并查集解题时不需要实现一个完整的并查集,根据题目要求实现需要用到的逻辑即可。
等式方程的可满足性
等式方程的可满足性
题目描述:
给定一个由表示变量之间关系的字符串方程组成的数组,每个字符串方程
e
q
u
a
t
i
o
n
s
[
i
]
equations[i]
equations[i] 的长度为4,并采用两种不同的形式之一:“
a
a
a==
b
b
b” 或 “
a
a
a!=
b
b
b”。在这里
a
a
a 和
b
b
b 是小写字母(不一定不同),表示单字母变量名。
只有当可以将整数分配给变量名,以便满足所有给定的方程时才返回
t
r
u
e
true
true ,否则返回
f
a
l
s
e
false
false 。
解题步骤:
- 定义一个长度为26(变量为小写字母)的数组充当并查集,并将数组中的元素初始化为-1,表示各个字母只有自己等于自己。
- 根据字符串方程组中的等式,对并查集中的各个集合进行合并(每个集合中的元素都是相等的)。
- 根据并查集,对字符串方程组中的不等式进行验证,如果两个不相等的变量出现在同一个集合中,则返回 f a l s e false false 。
代码如下:
class Solution {
public:
bool equationsPossible(vector<string>& equations) {
//1、初始化并查集
vector<int> ufs(26, -1);
auto findRoot = [&ufs](int x)->int {
int parent = x;
while (ufs[parent] >= 0) {
parent = ufs[parent];
}
return parent;
};
//2、根据字符串方程组中的等式合并集合
for (const string& s : equations) {
if (s[1] == '=') { //等式
int parent1 = findRoot(s[0] - 'a'), parent2 = findRoot(s[3] - 'a');
if (parent1 != parent2) { //需要合并
ufs[parent2] = parent1;
}
}
}
//3、根据并查集验证字符串方程组中的不等式
for (const string& s : equations) {
if (s[1] == '!') { //不等式
int parent1 = findRoot(s[0] - 'a'), parent2 = findRoot(s[3] - 'a');
if (parent1 == parent2) { //在同一个集合
return false;
}
}
}
return true;
}
};