文档章节

并查集(Union-Find)

o
 osc_z1hvg4cu
发布于 2018/04/24 22:07
字数 1092
阅读 7
收藏 0

精选30+云产品,助力企业轻松上云!>>>

一、基本操作:

1、Find:当且仅当两个元素属于相同的集合时,返回相同的名字

2、Union:将两个不相交的集合合并为一个不想交的集合。

应用:在等价关系中,判断两个元素之间是否有关系或者添加等价关系。

二、基本数据结构

1、Quick-Find实现

采用一个数组保存每个等价类的名字,这种实现下Find的复杂度为O(1),而Union实现的复杂度为O(n)。

例如Union(i,j):Union操作需要遍历整个数组,将所有为j的元素改为i。

 1 public class ADTQuickFind {
 2     private int[] id;
 3     private int size;
 4     public ADTQuickFind(int size){
 5         this.size = size;
 6         id = new int[size];
 7         //初始化默认所有节点不联通
 8         for(int i = 0; i < size; i++)
 9             id[i] = i;
10     }
11 
12     public int find(int p){
13         //p的值出现异常
14         if(p < 0 || p >= size)
15             return  -1;
16         return id[p];
17     }
18 
19     public void Union(int p, int q){
20         int pId = find(p);
21         int qId = find(q);
22         if(pId == qId)
23             return;
24         for(int i = 0; i < size; i++){
25             if(id[i] == qId)
26                 id[i] = pId;
27 
28         }
29     }
30 
31     public boolean isRelated(int p, int q){
32         return find(p) == find(q);
33     }
34 }

如果最开始所有元素都不连通,那么最多执行N-1次Union运算,此时所有的元素都在一个等价类中,总的时间复杂度为O(n2)。

如果Find运算比较多的情况下,存在Ω(n2)次Find运算,那么平均每次Find或者Union的时间复杂度为O(1),但是如果Find的次数比较少,那么这种方法是不可以接受的。

2、Quick-Union实现

在数组中隐式地存储一个森林,每个数组对应的位置存储对应节点的父节点的编号,树根节点保存自己的编号。

Find:由于Find操作要求当且仅当两个元素在相同的集合时,作用在两个元素上的Find操作返回相同的名字。而返回元素的标记是什么并不重要,因此通过返回一个节点的根节点的编号代表节点所处等价类的编号。

Union:使一个节点的根指针指向另一棵树的根节点。

 1 public class ADTQuickUnion {
 2     int[] parent;
 3     int size;
 4     public ADTQuickUnion(int size){
 5         this.size = size;
 6         parent = new int[size];
 7         for(int i = 0; i < size; i++)
 8             parent[i] = i;
 9     }
10     public int find(int p){
11         if(p < 0 || p >= size)
12             return -1;   //出现异常值
13         while(parent[p] != p)
14             p = parent[p];
15         return p;
16     }
17     public void union(int p, int q){
18         int pId = find(p);
19         int qId = find(q);
20         if(pId == qId)
21             return;
22         parent[qId] = pId;
23     }
24     public boolean isRelated(int p, int q){
25         return find(p) == find(q);
26     }
27 }

算法中执行Find操作花费的时间与节点的深度成正比,最坏情况下,会建立一个深度为N-1的树,使用一次Find的最坏情形运行时间为O(n)。

3、QuickUnionBetter实现

在Union操作中,将元素个数较少的树插到元素个数较多的树的根节点上。

 1 public class ADTQuickUnionBetter {
 2     private int[] parent;
 3     private int[] mSize;
 4     private int size;
 5     public ADTQuickUnionBetter(int size){
 6         this.size = size;
 7         parent = new int[size];
 8         mSize = new int[size];
 9         for(int i = 0; i < size; i++){
10             parent[i] = i;
11             mSize[i] = 1;
12         }
13     }
14     public int find(int p){
15         if(p < 0 || p >= size)
16             return -1;  //表明出现异常值
17         while(p != parent[p])
18             p = parent[p];
19         return p;
20     }
21     public void union(int p, int q){
22         int pId = find(p);
23         int qId = find(q);
24         if(pId == qId)
25             return;
26         if(mSize[pId] < mSize[qId]){
27             parent[pId] = qId;
28             mSize[qId] = mSize[pId] + mSize[qId];
29         }
30         else{
31             parent[qId] = pId;
32             mSize[pId] = mSize[qId] + mSize[pId];
33         }
34     }
35     public boolean isRelated(int p, int q){
36         return find(p) == find(q);
37     }
38 }

可以证明,任何节点的深度不会超过log(n),由于随着深度每次随着Union的结果而增大1时,该节点被置于节点数至少为原先两倍大的树上。

因此Find操作的时间复杂度为O(log(n)),连续M次操作的时间复杂度为O(MlogN),平均时间得到证明为O(M)时间,为线性的。

4、Find中优化路径压缩优化路径压缩

1 public int find(int p){
2     if(p < 0 || p >= size)
3         return -1;  //异常值
4     while(p != parent[p]){
5         parent[p] = parent[parent[p]];
6         p = parent[p];
7     }
8     return p;
9 }

 

o
粉丝 0
博文 500
码字总数 0
作品 0
私信 提问
加载中
请先登录后再评论。

暂无文章

格式编号始终显示2个小数位 - Format number to always show 2 decimal places

问题: I would like to format my numbers to always display 2 decimal places, rounding where applicable. 我想将数字格式化为始终显示2个小数位,并在适用的情况下四舍五入。 Examples...

富含淀粉
今天
22
0
Docker可视化工具Portainer

1 前言 从没想到Docker也有可视化的工具,因为它的命令还是非常清晰简单的。无聊搜了一下,原来已经有很多Docker可视化工具了。如DockerUI、Shipyard、Rancher、Portainer等。查看对比了一番...

南瓜慢说
今天
20
0
日志系统新贵 Loki,真香!!

最近,在对公司容器云的日志方案进行设计的时候,发现主流的ELK或者EFK比较重,再加上现阶段对于ES复杂的搜索功能很多都用不上最终选择了Grafana开源的Loki日志系统,下面介绍下Loki的背景。...

庞陆阳
今天
14
0
jQuery获取select onChange的值 - jQuery get value of select onChange

问题: I was under the impression that I could get the value of a select input by doing this $(this).val(); 我的印象是我可以通过执行$(this).val();来获取选择输入的值$(this).val()......

javail
今天
13
0
道翰天琼解密宇宙信息大脑三者最核心奥秘,破解认知智能基础理论(群聊形式)

三体论是探索研究宇宙,信息和人类大脑三者关系的理论体系。是认知智能的奠基理论体系之一。宇宙和信息,信息和人类大脑,人类大脑和宇宙,三者之间存在着某种未被完全揭示的奥秘。三体论的核...

jackli2020
今天
15
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部