文档章节

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

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

© 著作权归作者所有

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

没有更多内容

加载失败,请刷新页面

加载更多

下一页

[雪峰磁针石博客]python3快速入门教程1 turtle绘图-2函数

菲波那契序列: >>> # Fibonacci series:... # the sum of two elements defines the next... a, b = 0, 1>>> while b < 10:... print(b)... a, b = b, a+b...112......

python测试开发人工智能安全
今天
0
0
java环境变量配置最正确的方式

原贴:https://blog.csdn.net/qq_40007997/article/details/79784711,十分详细,亲测有效

kitty1116
今天
0
0
49.Nginx防盗链 访问控制 解析php相关 代理服务器

12.13 Nginx防盗链 12.14 Nginx访问控制 12.15 Nginx解析php相关配置(502的问题) 12.16 Nginx代理 扩展 502问题汇总 http://ask.apelearn.com/question/9109 location优先级 http://blog....

王鑫linux
今天
1
0
Nginx防盗链、访问控制、解析php相关配置、Nginx代理

一、Nginx防盗链 1. 编辑虚拟主机配置文件 vim /usr/local/nginx/conf/vhost/test.com.conf 2. 在配置文件中添加如下的内容 { expires 7d; valid_referers none blocked server_names *.tes......

芬野de博客
今天
0
0
spring EL 和资源调用

资源调用 import org.springframework.beans.factory.annotation.Value;import org.springframework.context.annotation.PropertySource;import org.springframework.core.io.Resource;......

Canaan_
今天
1
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部