微信公众号如何运营与推广,aso优化报价,wordpress网站百度搜索吗,wordpress怎么做后端目录 一. 并查集的概念
二. 并查集的模拟实现
2.1 并查集类的声明
2.2 并查集的实现
三. 路径压缩
四. 总结 一. 并查集的概念
在生活中#xff0c;我们经常需要对某一些事物进行归类处理#xff0c;即#xff1a;将N个不同的元素划分为几个互不相交的集合。在初始状态…目录 一. 并查集的概念
二. 并查集的模拟实现
2.1 并查集类的声明
2.2 并查集的实现
三. 路径压缩
四. 总结 一. 并查集的概念
在生活中我们经常需要对某一些事物进行归类处理即将N个不同的元素划分为几个互不相交的集合。在初始状态每个元素都属于一个独立的集合在归一合并的过程中经常需要查找某个元素属于哪一个集合实现上面功能的数据结构称之为并查集。
举一个生活中的例子假设小卖部了有如下货物苹果、香蕉、橘子、面包、薯片、牙膏、毛巾等一开始进货的时候这些货物是散装进货的没有归类。一般而言我们会将苹果、香蕉、橘子归类为水果将面包和薯片归为零食将牙膏和毛巾归为洗漱用品这就相当于并查集查找元素所属的几何并进行归类的过程。初步归类后继续将水果和零食统一归类为食物这相当于合并两个类并查集可以实现对类的合并。
并查集本质上是通过多颗树森林来实现的每一颗树都表示一个独立的集合使用双亲法表示树结构即每个节点仅保存其父亲节点。如图1.1所示将1~9十个数字分为三个集合分别为{0,5,6,9}、{1,4,7}、{2,3,8}用三棵树表示对应关系取{...}中第一个数据为根节点使用vectorint数组来实现双亲法表示树状结构假设数据与vector下标直接对应那么并查集划分集合的过程为
先将vectorint中每个元素都设为-1表示每个元素属于独立的集合。开始进行归一化对于每个叶子节点查找其根节点根节点值-1叶子节点位置处值为其父亲节点的下标。归类完成后根节点下标处的值为负数叶子节点下标处的值0。对于叶子节点下标处的负数值设其为rootVal有abs(rootVal) 本集合的数据个数。 图1.1 并查集归类 如图1.2所示将图1.1中的{0,5,6,9}和{1,4,7}归为一类那么1就变为了0的孩子节点合并后的几集合以0为根节点有7个元素因此vectorint下标为0的位置处元素变为了-1而原来下标为1的位置处的值变为合并后其父亲节点的值的下标即0。 图1.2 并查集合并集合 二. 并查集的模拟实现
2.1 并查集类的声明
我们假设并查集要管理的元素值从1~N不考虑模板类型数据和vectorint下标的映射情况根据第一节的内容一个并查集类应当以下成员变量和接口
std::vectorint _ufs 用于以双亲表示法记录每一颗树每一个集合。构造函数 给定数据量将_ufs中的元素全部初始化为-1。int FindRoot(int x)查找元素x所属的根在_ufs中的下标。void Union(int x1, int x2) 将x1和x2所在的集合合并为一个集合。size_t Size() 统计并查集内集合的个数。析构函数 采用编译器默认生成的析构函数即可。
代码2.1并查集类UnionFindSet的声明UnionFindSet.hpp头文件
#pragma once
#include iostream
#include vector
#include algorithm// 并查集
class UnionFindSet
{
public:UnionFindSet(size_t size);int FindRoot(int x); // 查找某个元素属于哪个集合根下标void Union(int x1, int x2); // 合并两个集合size_t Size() const; // 统计并查集内集合的个数private:std::vectorint _ufs;
};
2.2 并查集的实现
构造函数给定数据量size将_ufs初始化为函数size个值为-1的线性表表示每个元素都属于一个独立的集合。根查找函数int FindRoot(int x)本质上为查找元素属于哪一个集合前面提到根下标处的元素为负数因此只需要不断更新x _ufs[x]直到_ufs[x] x然后将x返回即可。集合合并函数void Union(int x1, int x2)先查找两个元素的根root1和root2如果root1 root2成立则表明两个元素属于同一集合这种情况下直接返回即可。如果root1 ! root2那么就让_ufs[root1] _ufs[root2]这样根节点下标位置处的绝对值就是集合中元素的个数然后再执行_ufs[root2] _ufs[root1]表示跟新被合并集合的根节点。统计集合个数函数size_t Size()统计根节点个数即_ufs中小于0的元素的个数即可。
代码2.2并查集的实现UnionFindSet.cpp源文件
#define _CRT_SECURE_NO_WARNINGS 1#include UnionFindSet.hppUnionFindSet::UnionFindSet(size_t size): _ufs(size, -1)
{ }// 查找某个元素属于哪个集合根下标
int UnionFindSet::FindRoot(int x)
{// 循环查找直到_ufs[x] 0while (_ufs[x] 0){x _ufs[x];}return x;
}// 合并两个集合
void UnionFindSet::Union(int x1, int x2)
{int root1 FindRoot(x1);int root2 FindRoot(x2);if (root1 root2){return;}if (root1 root2){std::swap(root1, root2);}_ufs[root1] _ufs[root2];_ufs[root2] root1;
}// 统计并查集内集合的个数
size_t UnionFindSet::Size() const
{// 遍历_ufs统计小于0的元素的个数size_t count 0;for (const auto x : _ufs){if (x 0) count;}return count;
}
三. 路径压缩
如果并查集中毒元素数量过多那么每次查找根节点都需要花费较大的成本那么就需要采取适当的手段来进行路径压缩。
路径压缩最常用的方法每当查找完一个元素所属集合的根节点后都将这个元素的父亲节点直接设备根节点这样当第二次查找这个元素的根节点时就只需要向上查找一层即可。
如图3.1所示假设要查找5的根节点并进行路径压缩只需要在找到5的根节点0后将5挂在0的下面即可。当然如果元素的数量不是很大就没必要考虑路径压缩因为路径压缩本身也存在资源消耗。 图3.1 路径压缩 四. 总结
并查集是通过双签法实现多颗树森林来进行数据分类的数据结构。并查集能够实现的功能包括查找元素所属集合根节点、合并集合、统计集合数目。如果并查集中元素的数目过多那么应当进行路径压缩。
