您现在的位置是:首页 >技术交流 >高阶数据结构 ——— 并查集网站首页技术交流

高阶数据结构 ——— 并查集

2021dragon 2023-06-21 08:00:03
简介高阶数据结构 ——— 并查集

并查集

  • 并查集是一种树型的数据结构,用于处理一些不相交集合的合并及查询问题。
  • 并查集通常用森林来表示,森林中的每棵树表示一个集合,树中的结点对应一个元素。

说明一下: 虽然利用其他数据结构也能完成不相交集合的合并及查询,但在数据量极大的情况下,其耗费的时间和空间也是极大的。

并查集的原理

并查集的原理

以朋友圈为例,现在有10个人(从0开始编号),刚开始这10个人互不认识,所以各自属于一个集合。如下:

在这里插入图片描述

并查集会用一个数组来表示这10个人之间的关系,数组的下标对应就是这10个人的编号,刚开始时数组中的元素都初始化为-1。如下:

在这里插入图片描述

说明一下:

  • 数组中某个位置的值为负数,表示该位置是树的根,这个负数的绝对值表示的这棵树(集合)中数据的个数,因为刚开始每个人各自属于一个集合,所以将数组中的位置都初始化为-1。

后来这10个人之间通过相互认识,最终形成了三个朋友圈。如下:

在这里插入图片描述

此时并查集数组中各个位置的值如下:

在这里插入图片描述

说明一下:

  • 数组中某个位置的值为非负数,表示该位置不是树的根,这个非负数的值就是这个结点的父结点的编号。

后来4号和8号又通过某种机遇互相认识了,这时他们所在的两个集合就需要进行合并,最终就变成了两个朋友圈。如下:

在这里插入图片描述

需要注意的是,在根据两个元素合并两个集合时,需要先分别找到这两个元素所在集合的根结点,然后再将一个集合合并到另一个集合,并且合并后需要更新数组中根结点的值。

示意图如下:

在这里插入图片描述

合并集合找根结点的原因:

  1. 如果这两个元素所在集合的根结点相同,说明这两个元素本身就在同一个集合,无需合并。
  2. 合并集合后需要更新这两个集合的根结点的值。

而要判断两个元素是否在同一个集合,也就是判断这两个元素所在集合的根结点是否相同。

并查集的实现

并查集的实现

实现并查集时通常会实现如下接口:

  • 初始化并查集。
  • 查找元素所在的集合。
  • 合并两个元素所在的集合。
  • 获取并查集中集合的个数。

代码如下:

//并查集
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]);
}

合并两个元素所在的集合

合并两个元素所在的集合

合并逻辑如下:

  1. 分别找到两个元素所在集合的根结点。
  2. 如果这两个元素所在集合的根结点相同,则无需合并,如果这两个元素所在集合的根结点不同,则将小集合合并到大集合上。
  3. 将小集合根结点的值累加到大集合的根结点上,使得大集合根结点的值的绝对值等于两个集合中元素的总数。
  4. 将小集合根结点的值改为大集合根结点的编号,也就是让小集合的根结点作为大集合根结点的孩子,使得两个集合变为一个集合。

代码如下:

//合并两个元素所在的集合
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 表示二者不直接相连。返回矩阵中省份的数量。

解题步骤:

  1. 定义一个长度为 n n n 的数组充当并查集,并将数组中的元素初始化为-1,表示各个城市各自是一个省份。
  2. 根据所给矩阵,对并查集中的各个集合进行合并。
  3. 并查集中集合的个数即为省份的数量。

代码如下:

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

解题步骤:

  1. 定义一个长度为26(变量为小写字母)的数组充当并查集,并将数组中的元素初始化为-1,表示各个字母只有自己等于自己。
  2. 根据字符串方程组中的等式,对并查集中的各个集合进行合并(每个集合中的元素都是相等的)。
  3. 根据并查集,对字符串方程组中的不等式进行验证,如果两个不相等的变量出现在同一个集合中,则返回 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;
    }
};
风语者!平时喜欢研究各种技术,目前在从事后端开发工作,热爱生活、热爱工作。