【C++数据结构】并查集的路径压缩

文章目录

前言
路径压缩

前言

以往出过一期并查集的简单入门：
一篇文章了解并查集

路径压缩

路径压缩实际上是在数据量太大的时候，访问一些数据可能在位于叶子位置，导致访问的效率不高，这个时候有两种方法进行提高效率：

两颗树合并的时候，节点少的树往节点多的树合并。目的：为了使节点层数增多的节点相对减少。
查找的时候对该路径上的节点进行路径压缩。目的：使更多的节点在第二层。
最好不要用递归的时候进行路径压缩，因为路径深可能导致栈溢出。

若在上图查找1，我们查找完之后图应该变为下面这样：
即1，2，3，8的处的索引都指向0（父亲），这样就进行了压缩，并且查找的时候本身就会去找根，所以开销不是很大。
while (_unionset[cur] >= 0)到0这个点的时候存储的就是负数，就会结束了。

FindRoot函数进行压缩，Union进行小树合并到大树。

#include
#include
#include
using std::map;
using std::vector;
//并查集是一个森林，一开始数组全部初始化为-1，代表每个人都是一颗独立的子树
//然后开始合并（PutInRange）,合并可以提供两个版本，一种是用编号进行合并，一种是用数值进行合并
class UnionFindSet
{
private:
	vector _unionset;
public:
	UnionFindSet(size_t n)
		:_unionset(n,-1)
	{}
	int FindRoot(int cur)
	{
		//找跟，是比较重要的环节
		int root = cur;
		while (_unionset[root] >= 0)
		{
			//根节点的值一定是负数
			root = _unionset[root];
		}
		//若数据量大，可以加上以下的压缩函数
		//合并的时候，该路径的所有节点都可以被合并
		while (_unionset[cur] >= 0)
		{
			//若更改当前位置的父亲节点，会丢失以前的父亲节点
			int pIndex = _unionset[cur];
			_unionset[cur] = root;
			cur = pIndex;
		}
		return root;
	}
	
	void Union(const int& index1, const int& index2)
	{
		int root1 = FindRoot(index1);
		int root2 = FindRoot(index2);
		//有可能两个树是在一颗树当中，此时倘若合并会出错
		if (root1 == root2)
			return;

		//这里可以小的合并给大的，因为层次深的节点就少了
		if (_unionset[root1] > _unionset[root2])
		{
			swap(root1, root2);
		}
		//相当于root1所在位置的节点更多，root2也变成了root1所在的一颗子树
		_unionset[root1] += _unionset[root2];
		_unionset[root2] = root1;
	}

	bool TestUnionSet(const int& v1, const int& v2)
	{
		int root1 = FindRoot(v1);
		int root2 = FindRoot(v2);
		//有可能两个树是在一颗树当中，此时倘若合并会出错
		if (root1 == root2)
			true;
		return false;
	}
};

结束了~

喜欢就收藏
认同就点赞
支持就关注
疑问就评论

【C++数据结构】并查集的路径压缩

C/C++/C#相关栏目本月热门文章