博主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
};
首先可以先实现,找到一个下标的根,后续的函数可以复用它:
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
};
判断两个数是否在同一集合,以及一共有几个集合,这两个函数比较简单,不做讲解. 合并两个集合先要找到这两个数的根,如果这两个数有相同的根就直接返回,否则就开始合并.合并的逻辑也非常简单,其中的if,else语句不是必须的
4. 并查集的应用
由于我是学生,所以我先给大家看看并查集在校招中考察的多不多,这道题: 省份数量是19年美团笔试的原题,并且今年24年的笔试疑似也出现过并查集解题. 除此之外, 华为考察算法和数据结构也比较厉害.其中的考点之一就有并查集:
并查集往往用于解决图上的问题，并查集只有两个操作，“并” 和 “查”，但是通过这两个操作可以派生出一些其他的应用：
图的连通性问题集合的个数集合中元素的个数
并且在后面学习图论的过程中,也会涉及到并查集的知识,会复用并查集的代码. 这也是我优先讲并查集的原因之一, 如果你没有学过并查集直接去搞图论,可能会十分吃力
5. 总结以及拓展
并查集只是高阶数据结构中的开胃菜,后面的数据结构会越来越难,请大家耐心学习
下期预告:图论
参考阅读
您阅读本篇文章共花了：
发表评论