文档章节

Union Find-并查集

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

码上生花,ECharts 作品展示赛正式启动!>>>

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

一般有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

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

© 著作权归作者所有

梦想游戏人
粉丝 43
博文 491
码字总数 194264
作品 0
成都
私信 提问
加载中
请先登录后再评论。
第三十一篇 玩转数据结构——并查集(Union Find)

1.. 并查集的应用场景 查看"网络"中节点的连接状态,这里的网络是广义上的网络 数学中的集合类的实现 2.. 并查集所支持的操作 对于一组数据,并查集主要支持两种操作:合并两个数据、判断两个...

osc_odyg6b92
2018/07/13
2
0
算法与数据结构基础 - 合并查找(Union Find)

Union Find算法基础 Union Find算法用于处理集合的合并和查询问题,其定义了两个用于并查集的操作: Find: 确定元素属于哪一个子集,或判断两个元素是否属于同一子集 Union: 将两个子集合并为...

osc_msepeizi
04/16
1
0
MySQL大表拆分多个表的方式(横向拆分和纵向拆分)及如何解决跨表查询效率问题

  大表分表后每个表的结构相同,可以用sql的union。比如a,b表结构相同可以通过union来联接 select * from aunion allselect * from bwhere ... 1、Union和Union All到底有什么区别   Uni...

古兰精
05/09
0
0
【从蛋壳到满天飞】JS 数据结构解析和算法实现-并查集(一)

前言 【从蛋壳到满天飞】JS 数据结构解析和算法实现,全部文章大概的内容如下: Arrays(数组)、Stacks(栈)、Queues(队列)、LinkedList(链表)、Recursion(递归思想)、BinarySearchTree(二分搜...

哎哟迪奥
2019/03/27
0
0
并查集(Union Find)的实现及代码应用

前言   之前我们在连通分量的个数那个题中提到了并查集,可是我们还是没有正式讲解并查集的使用方法,下面我们来正式讲一下并查集的使用及实现   我们要知道,并查集包含两部分,并(uni...

osc_pc30nqhx
2018/08/22
1
0

没有更多内容

加载失败,请刷新页面

加载更多

Java 项目工程搭建 --创建子模块(Spring Initializr)

一下篇,常用 Java 项目工程搭建 --创建子模块(依赖父工程) 也不算常用,常用的是 ctrl+c、ctrl+v ,哈哈 Package要手动改下,生成的很丑 选能支持 Alibaba Cloud 的版本 不然会跑到根目录...

osc_qheq8wav
21分钟前
13
0
C++指针相关问题

C++指针相关问题 一、总结 一句话总结: a、数组名是这个数组的首地址:a[3][4]:a int(*)[4]、&a int(*)[3][4]、a[0] int*、a[0][0] int b、int ** 表示指向指针的指针:int m = 1; int *p...

osc_35ne77sz
22分钟前
13
0
好兄弟仅用3年,就做到了架构师的位置,真心羡慕!经验分享给你

昨天跟好兄弟聊天,得知了他最近晋升了架构师的消息,是真的羡慕。要知道,我这个兄弟仅用了三年的时间,就做到了架构师的位置,真的优秀! 懂得多门主流编程语言如C++、Java、python等,可以...

osc_vnopwmym
22分钟前
13
0
C 实战练习题目40

题目:将一个数组逆序输出。 程序分析:用第一个与最后一个交换。 实例: 1 #include<stdio.h> 2 #define N 10 3 int main() 4 { 5 int a[N]={0,1,2,3,4,5,6,7,8,9}; 6 int i,...

osc_o1iwxx3z
24分钟前
29
0
C 实战练习题目36 – 求100之内的素数

题目:求100之内的素数。 程序分析:质数(prime number)又称素数,有无限个。一个大于1的自然数,除了1和它本身外,不能被其他自然数整除。 实例: 1 #include<stdio.h> 2 #include<mat...

osc_t4xzns0d
25分钟前
23
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部