当前位置:网站首页>并查集总结
并查集总结
2022-08-02 23:47:00 【明朗晨光】
1、简介
1)有若干个样本 a、b、c、d… 类型假设是 V
2)在并查集中一开始认为每个样本都在单独的集合里
3)用户可以在任何时候调用如下两个方法:
boolean isSameSet(V x, V y)
:查询样本x
和 样本y
是否属于一个集合void union(V x,V y)
:把x
和y
各自所在集合的所有样本合并成一个集合
4)isSameSet
和 union
方法的代价越低越好
2、并查集结构
1)每个节点都有一条往上指的指针
2)节点 a
往上找到的头节点,叫做 a
所在集合的代表节点
3)查询 x
和 y
是否属于同一个结合,就是看看找到的代表节点是不是一个
4)把 x
和 y
各自所在集合的所有点合并成一个集合,只需要小集合的代表点挂在大集合的代表点的下方即可
(可以用哈希表或者数组实现,虽然二者的时间复杂度一致,但是哈希表实现方式的常数比数组实现的常数大2倍左右,所以在数据量很大的时候,数组的实现方式用时更少)
3、并查集的优化
1)节点往上找代表节点的过程,把沿途的链变成扁平的 【路径压缩】
说明:比如 a->b->c->f
,即代表节点是 f
,那么则将 a
、b
、c
分别直接连到 f
,变成了a->f
、b->f
、c->f
2)小集合挂在大集合的下面 【按秩合并】
说明:小集合挂在大集合下,链的长度增长得比较慢。所谓大小集合就是集合的元素个数,元素个数多的叫做大集合,小的叫做小集合。
3)如果方法调用很频繁,那么单次调用的代价为 O ( 1 ) O(1) O(1),两个方法都如此
4、并查集的应用
- 解决两大块区域的合并问题
- 常用在图等领域中(连通性问题)
边栏推荐
- DB2数据库-获取表结构异常:[jcc][t4][1065][12306][4.26.14]CharConvertionException ERRORCODE=-4220,SQLSTATE=null
- 典型相关分析CCA计算过程
- C# 异步编程(async和await)
- 科研用Cholesterol-PEG-NHS,NHS-PEG-CLS,胆固醇-聚乙二醇-活性酯
- 【QT】自定义工程封装成DLL并如何调用(带ui界面的)
- js基础知识整理之 —— Math
- @GetMapping、@PostMapping、@PutMapping、@DeleteMapping的区别
- 2022第十一届财经峰会:优炫软件斩获双项大奖
- dataBinding的import导入
- d合并json
猜你喜欢
随机推荐
MySQL最大建议行数2000w, 靠谱吗?
Cholesterol-PEG-Acid,胆固醇-聚乙二醇-羧基保持在干燥、低温环境下
如何突破测试/开发程序员思维?一种不一样的感觉......
Merge two excel spreadsheet tools
CKAN教程之在 AWS 上部署 CKAN 应用程序
最近公共祖先(LCA)学习笔记 | P3379 【模板】最近公共祖先(LCA)题解
alibaba数据同步组件canal的实践整理
「PHP基础知识」隐式数据类型
Test | ali internship 90 days in life: from the perspective of interns, talk about personal growth
NLP commonly used Backbone model cheat sheet (1)
js基础知识整理之 —— 获取元素和命名规范
DB2数据库-获取表结构异常:[jcc][t4][1065][12306][4.26.14]CharConvertionException ERRORCODE=-4220,SQLSTATE=null
优秀论文以及思路分析01
公司招个程序员,34岁以上两年一跳的不要,开出工资以为看错了
线性DP
嵌入式分享合集26
微信小程序实现lot开发09 接入微信登录
TensorFlow学习记录(一):基本介绍
精心整理16条MySQL使用规范,减少80%问题,推荐分享给团队
# DWD层及DIM层构建## ,220801 ,