【高阶数据结构(一)】并查集详解

码农世界 2024-05-20 前端 55 次浏览 0个评论

💓博主CSDN主页:杭电码农-NEO💓

⏩专栏分类:高阶数据结构专栏⏪

🚚代码仓库:NEO的学习日记🚚

🌹关注我🫵带你学习更多Go语言知识
🔝🔝

高阶数据结构

1. 前言
2. 并查集的原理
3. 并查集的实现
4. 并查集的应用
5. 总结以及拓展
1. 前言

本系列会带大家走进高阶数据结构的学习, 其中包括并查集,图论, LRU cache, B树, B+树, B*树, 跳表. 其中, 图论中讲解的时间最长, 包括邻接表, 邻接矩阵, 广度优先遍历, 深度优先遍历, 最小生成树, 以及prim算法, dijkstra算法, bellman-Ford算法, Floyd-wars hall算法. 高阶数据结构属于拓展内容, 建议把基础掌握好后再学

本章重点:

本篇文章着重讲解并查集的原理, 并查集的实现(CPP),以及并查集的应用

2. 并查集的原理

在一些应用问题中，需要将n个不同的元素划分成一些不相交的集合。开始时，每个元素自成一个单元素集合，然后按一定的规律将归于同一组元素的集合合并。在此过程中要反复用到查询某一个元素归属于那个集合的运算。适合于描述这类问题的抽象数据类型称为并查集(union-find set)。

比如, 公司招的10个人当中有4人是北京的,三人是上海的,3人是深圳的. 那么他们就可以被分为三个不同的集合. 现在将他们进行编号(0~9),然后来看看如何将他们进行分组(为什么初始值为-1,后面再解释)

北京学生: 0,6,7,8.上海学生: 1,4,9.深圳学生: 2,3,5
假如选出0,1,2号学生作为小组的组长

现在需要在数组中,表示三个分组, 不卖关子,直接讲解并查集的原理. 当组长的人的位置的值是负数,-n代表这个组有n个人. 而非组长的成员的位置的值存储的是组长的下标,这样说可能有点抽象,下面来画个图看看

北京小组的组长是0,它的值是-4代表此小组有四个人.6,7,8是0的组员,所以它们存储的值是0,也就是组长的下标. 所以刚开始初始值为-1,代表每一个数都自成一个集合

现在出现一个情况, 由于北京的同学和上海的同学经常在一起玩耍, 所以久而久之他们就很熟了,就想着将这两个分组合并.于是出现了以下的情况:

此时,下标为1的位置应该存储它的父亲,也就是0,下标为4.9的位置不能直接存储0,而是应该存储1,因为1才是他们的直系父亲. 可以用下图来表示:

你可以窥探到,下标为0的值从-4变为-7,而下标为1的值从-3变为0,实际上就为我们后面的手撕并查集提供了思路

3. 并查集的实现

在进行并查集实现时,应该要拥有这几个基础功能函数: 找到一个下标的根, 合并两个集合, 判断两个树是否在同一个集合. 计算此并查集一共有几个集合.

并查集的本质是数组,所以可以这样定义结构:
```
class UnionFindSet
{
public:
	UnionFindSet(size_t n):_ufs(n,-1)//初始化数组,初始值设为-1
private:
	vector _ufs;	
};
```
首先可以先实现,找到一个下标的根,后续的函数可以复用它:
```
int FindRoot(int x)//找到一个下标的根
{
	int parent = x;
	while (_ufs[parent] >= 0)
		parent = _ufs[parent];
	//路径压缩.下次查找时效率就高了(压缩当前节点以及它的父亲节点)
	while (_ufs[x] >= 0)
	{
		int tmp = _ufs[x];
		_ufs[x] = parent;
		x = tmp;
	}
	return parent;
}
```
这份代码可以分为两步,第一步就是在找它的根,就是一直向前找直到遇见负数.第二部分的代码在进行路径压缩工作,若是有多个集合进行合并,那么我们的树可能就会很高,查找最下面的树的根时,就会出现效率低下的问题,所以进行路径压缩很有必要. 关于路径压缩的原理如下:

下次再查找4的时候,就优化了时间

接下来的代码就简单了:
```
#pragma once
#include
#include
using namespace std;
class UnionFindSet
{
public:
	UnionFindSet(size_t n):_ufs(n,-1)
	{}
	void Union(int x1, int x2) //合并两个集合
	{
		int root1 = FindRoot(x1);
		int root2 = FindRoot(x2);
		if (root1 == root2) return;
		if (_ufs[root1] < _ufs[root2])
		{
			_ufs[root1] += _ufs[root2];
			_ufs[root2] = root1;
		}
		else
		{
			_ufs[root2] += _ufs[root1];
			_ufs[root1] = root2;
		}
	}
	int FindRoot(int x)//找到一个下标的根
	{
		int parent = x;
		while (_ufs[parent] >= 0)
			parent = _ufs[parent];
		//路径压缩.下次查找时效率就高了(压缩当前节点以及它的父亲节点
		while (_ufs[x] >= 0)
		{
			int tmp = _ufs[x];
			_ufs[x] = parent;
			x = tmp;
		}
		return parent;
	}
	bool SameSet(int x1, int x2)//判断这两个数是否在同一个集合
	{
		return FindRoot(x1) == FindRoot(x2);
	}
	size_t SetSize()//这个并查集一共有几个集合
	{
		size_t size = 0;
		for (auto x : _ufs)
			if (x < 0)
				size++;
		return size;
	}
private:
	vector _ufs;	
};
```
判断两个数是否在同一集合,以及一共有几个集合,这两个函数比较简单,不做讲解. 合并两个集合先要找到这两个数的根,如果这两个数有相同的根就直接返回,否则就开始合并.合并的逻辑也非常简单,其中的if,else语句不是必须的

4. 并查集的应用

由于我是学生,所以我先给大家看看并查集在校招中考察的多不多,这道题: 省份数量是19年美团笔试的原题,并且今年24年的笔试疑似也出现过并查集解题. 除此之外, 华为考察算法和数据结构也比较厉害.其中的考点之一就有并查集:

并查集往往用于解决图上的问题，并查集只有两个操作，“并” 和 “查”，但是通过这两个操作可以派生出一些其他的应用：
- 图的连通性问题
- 集合的个数
- 集合中元素的个数
  
  并且在后面学习图论的过程中,也会涉及到并查集的知识,会复用并查集的代码. 这也是我优先讲并查集的原因之一, 如果你没有学过并查集直接去搞图论,可能会十分吃力
  
  5. 总结以及拓展
  
  并查集只是高阶数据结构中的开胃菜,后面的数据结构会越来越难,请大家耐心学习
  
  🔎 下期预告:图论 🔍