文档章节

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

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

© 著作权归作者所有

共有 人打赏支持
梦想游戏人
粉丝 35
博文 435
码字总数 123998
作品 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

没有更多内容

加载失败,请刷新页面

加载更多

20181213 上课截图

小丑鱼00
10分钟前
0
0
nginx+php-fpm配置后页面显示空白的解决方法以及用nginx和php-fpm解决“502 Bad Gateway”问题

https://stackoverflow.com/questions/15423500/nginx-showing-blank-php-pages For reference, I am attaching my location block for catching files with the .php extension: location ~......

Yao--靠自己
17分钟前
1
0
mac 没声音

somehow不时就会出现这种情况。之前都得重启。 其实可以直接在terminal里打以下命令: sudo kextunload /System/Library/Extensions/AppleHDA.kext sudo kextload /System/Library/Extension...

dubox
33分钟前
1
0
看完让你彻底搞懂Websocket原理

作者:Ovear 链接:https://www.zhihu.com/question/20215561/answer/40316953 来源:知乎 著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。 额。。最高票答案没答到点...

时刻在奔跑
48分钟前
2
0
Spring Cloud Stream消费失败后的处理策略(一):自动重试

之前写了几篇关于Spring Cloud Stream使用中的常见问题,比如: 如何处理消息重复消费 如何消费自己生产的消息 下面几天就集中来详细聊聊,当消息消费失败之后该如何处理的几种方式。不过不论...

程序猿DD
50分钟前
0
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部