文档章节

Union Find-并查集

梦想游戏人
 梦想游戏人
发布于 2017/07/29 11:27
字数 537
阅读 11
收藏 0

并查集是在各个不相交集合中查找某元素存在否,可以接近常数级查找例如,图的连通性,最近公共祖先等问题。一般用森林 数组实现。

一般有2个操作,查找(find)和合并(union)

查找:从集合中查找元素x是否存在。

合并:如果2个集合不想交则可以合并操作,一般方法是高度低的合并到高度高的。

初始化每个元素都可以是一个单独的集合,然后不断引入关系来合并他们

问题引入:

若某个家族人员过于庞大,要判断两个是否是亲戚,确实还很不容易,给出某个亲戚关系图,求任意给出的两个人是否具有亲戚关系。 规定:x和y是亲戚,y和z是亲戚,那么x和z也是亲戚。如果x,y是亲戚,那么x的亲戚都是y的亲戚,y的亲戚也都是x的亲戚。

简单地看是2个元素xy在这个庞大的关系网络中是否有是亲戚关系,每个成员都可以看做是一个元素,常规的图论做法深度搜索 代价比较大。

并查集很适合这种情况下的查找判断

可以通过hash来简化这个过程,元素按照1234567 来区分,对应数组0123456下标,存储的内容就是父节点,表达的意思是和其父节点是亲戚关系。

初始化,数组初始存储值是其本身,表示没有关系

初始数组0123456,其中456为第二个集合

输入ab,数组变为0023456,1的父节点是0表示他们是亲戚关系

输入bd,数组变为0021456,3的父节点是1他们是亲戚关系

输入ac,数组变为0001456,2的父节点是0

第一组集合输入完毕,对于第二组集合

输入ef,数组变为0001446

输入fg,数组变为0001445

上述输入是关于数组的合并操作,对应代码

© 著作权归作者所有

共有 人打赏支持
梦想游戏人
粉丝 36
博文 429
码字总数 122078
作品 0
成都
SQL集合运算:差集、交集、并集

1、差集( except ) select a from t_a except select a from t_b -- 也可写作: select a from ta where a not in (select a from tb) -- 多个字段时: select a,b from t_a except select ......

颖辉小居
2016/11/04
97
0
SQL集合运算:差集、交集、并集

1、差集( except ) select a from t_a except select a from t_b -- 也可写作: select a from ta where a not in (select a from tb) -- 多个字段时: select a,b from t_a except select ......

赵帅A
2016/04/27
61
0
Union-Find Set 并查集

v2-b87b6b4929022f7581ccd6e58df4a1fc_r.png ![TOC] 并查集操作的复杂度是log n。是一个衰减非常快的函数,即使n 很大,log n的结果也接近一个常数,不会超过5。 其实并查集顾名思义就是有“...

陈黎栋知心话
2017/12/15
0
0
使用explain来分析MySQL 查询性能

为了在MySQL中写出高效的SQL脚本,我们的SQL必须时时都要用来检查其执行计划,时时调整。 的使用方法为: 比如下面这条SQL 在MySQL执行完以后如下所示: 下面说一下这些列都代表什么: sele...

古城痴人
2015/08/19
0
0
LeetCode 721. Accounts Merge

原题 Given a list accounts, each element accounts[i] is a list of strings, where the first element accounts[i][0] is a name, and the rest of the elements are emails representing......

likewind1993
2017/11/17
0
0

没有更多内容

加载失败,请刷新页面

加载更多

关于组件化的最初步

一个工程可能会有多个版本,有国际版、国内版、还有针对各种不同的渠道化的打包版本、这个属于我们日常经常见到的打包差异化版本需求。 而对于工程的开发,比如以前的公司,分成了有三大块业...

DannyCoder
28分钟前
0
0
Spring的Resttemplate发送带header的post请求

private HttpHeaders getJsonHeader() { HttpHeaders headers = new HttpHeaders(); MediaType type = MediaType.parseMediaType("application/json; charset=UTF-8"); ......

qiang123
昨天
2
0
Spring Cloud Gateway 之 Only one connection receive subscriber allowed

都说Spring Cloud Gateway好,我也来试试,可是配置了总是报下面这个错误: java.lang.IllegalStateException: Only one connection receive subscriber allowed. 困扰了我几天的问题,原来...

ThinkGem
昨天
25
0
学习设计模式——观察者模式

1. 认识观察者模式 1. 定义:定义对象之间一种一对多的依赖关系,当一个对象状态发生变化时,依赖该对象的其他对象都会得到通知并进行相应的变化。 2. 组织结构: Subject:目标对象类,会被...

江左煤郎
昨天
2
0
emoji

前言:随着iOS系统版本的升级,对原生emoji表情的支持也越来越丰富。emoji表情是unicode码中为表情符号设计的一组编码,当然,还有独立于unicode的另一套编码SBUnicode,在OS系统中,这两种编...

HeroHY
昨天
3
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部