首页 > 代码库 > 并查集

并查集

2024-07-06 16:38:35   239人阅读

并查集是用来管理元素分组情况的数据结构。


并查集可以高效的进行如下操作。
  • 查询元素a和元素b是否属于同一组。
  • 合并元素a和元素b所在的组。
并查集不能进行分割操作。

并查集的实现就是三个函数
  • 初始化
  • 合并
  • 查寻
在树形结构中都存在退化的现象，为了让并查集避免退化我们记录了树的高度，在合并的时候我们将高度低的树加入到高度高的树上。
我们还用了路径压缩（好厉害的名字） 其实就是

从图中可以很清晰的看明白。
现在我们来写构造并查集的代码
第一个初始化：
void init(int x)
{
	for(int i=0;i<=x;i++)
	{
		par[i]=i;
		ran[i]=0;
	}
}

就是将所有的点都是 自己属于一类，与别人没有关系 ，自己的父节点是自己；


接下来是查找函数
int find(int x)
{
	if(par[x]==x)
		return x;
	else
		return par[x]=find(par[x]);
}

查找的是自己最上面的节点是谁，也就是说，自己属于哪一类；


最后我们来附上最牛掰的 合并函数：

void unite(int x,int y)
{
	int xx = find(x);
	int yy = find(y);
	if(xx==yy)//先找出父节点 如果相同就返回；
		return ;
	if(ran[x]>ran[y])//如果不相同就把矮的树加到高的树上，如果相同就直接把一颗加到另一颗上；
		par[y]=x;
	else if(ran[y]>ran[x])
		par[x]=y;
	else
	{
		par[y]=x;
		ran[x]++;
	}
}



好了  到这我们的并查集就基本结束了。

好了感谢自己坚持


联系
我们