Contents
  1. 1. 介绍
  2. 2. 适用场景
  3. 3. 实现思路
    1. 3.1. Simple Find 操作
    2. 3.2. Simple Union 操作
    3. 3.3. 优化
    4. 3.4. Find 操作
    5. 3.5. Union 操作
    6. 3.6. 时间复杂度
  4. 4. Refer

介绍

在计算机科学中,并查集是一种树型的数据结构,其保持着用于处理一些不相交集合(Disjoint Sets)的合并及查询问题。有一个联合-查找算法(union-find algorithm)定义了两个操作用于此数据结构:

Find:确定元素属于哪一个子集。它可以被用来确定两个元素是否属于同一子集。

Union:将两个子集合并成同一个集合。

适用场景

适合于判断,给出一组结点,判断他们是否联通。

实现思路

  1. 建立n个分组,每个分组代表一堆可以互相联通的结点。
  2. 遍历每对结点,找到他们各自所属的分组A, B
  3. 如果A != B,则将A, B分组union起来,表示A, B分组联通了
  4. 如果A == B,则跳过

Simple Find 操作

用 group[] 数组来判断某个id属于的组。初始状态时,每个id都属于不同的组。

1
2
for(int i = 0; i < size; i++)
group[i] = i;

Simple Union 操作

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public void union(int p, int q) {
// get the groupId of every node
int pId = find(p);
int qId = find(q);
// the two nodes are connected, return
if (pId == qId) {
return;
}
// union the two nodes, change groupId
for (int i = 0; i < id.length; i++) {
if (group[i] == pId) {
group[i] = qId;
}
}
}

优化

上面最后一步的union操作存在性能问题,即每次都需要改变其中一个分组中的所有结点的分组id。优化的做法是,用一颗树来表示每个分组,树的根节点表示当前组的id。

但如果用树来表示会引入一个问题,即可能存在树退化为链表的情况,这样一来,每一次加入一个结点再找根结点也会很耗时,没有达到优化的目的。
针对树可能退化为链表的解决方案是,每次合并树时,总是将矮的树挂到高的树下。这种方式也称为「按秩合并」

除了使用树来优化union性能以外,还有一种方式,称为「路径压缩」,即 Find 递归地经过树,改变每一个节点的引用到根节点。得到的树将更加扁平,为以后直接或者间接引用节点的操作加速。

总结:

  1. 使用树来存储分组,Union时「按秩合并」
  2. 「路径压缩」,Find时改变每一个节点的引用到根节点

Find 操作

1
2
3
// store every tree's size
for (int i = 0; i < N; i++)
size[i] = 1;
1
2
3
4
5
6
7
8
private int find(int p)
{
if(p != group[p]){
group[p] = find(group[p])
}
return group[p]
}

Union 操作

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public void union(int p, int q)
{
int i = find(p);
int j = find(q);
if (i == j) {
return;
}
if (size[i] < size[j]) {
group[i] = j;
size[j] += size[i];
} else {
group[j] = i;
size[i] += size[j];
}
}

时间复杂度

Statement: If m operations, either Union or Find, are applied to n elements, the total run time is O(m logn), where log is the iterated logarithm.
Proof of O(logn) time complexity of union-find: https://en.wikipedia.org/wiki/Proof_of_O\(logn)_time_complexity_of_union%E2%80%93find

Refer

https://zh.wikipedia.org/wiki/%E5%B9%B6%E6%9F%A5%E9%9B%86
http://blog.csdn.net/dm_vincent/article/details/7655764
https://en.wikipedia.org/wiki/Proof_of_O(log*n)_time_complexity_of_union%E2%80%93find

Contents
  1. 1. 介绍
  2. 2. 适用场景
  3. 3. 实现思路
    1. 3.1. Simple Find 操作
    2. 3.2. Simple Union 操作
    3. 3.3. 优化
    4. 3.4. Find 操作
    5. 3.5. Union 操作
    6. 3.6. 时间复杂度
  4. 4. Refer