UnionFind (Disjoint Sets)

I. Introduction

This data structure is used to solve “Dynamic Connectivity” problem.

1. Applications

Pixels in a digital photo.
Computers in a network.
Friends in a social network.
Transistors in a computer chip.
Elements in a mathematical set.
Variable names in Fortran program.
Metallic sites in a composite system.

2. API

61b和Algorithms两门课提供api的method名称虽然有差别，但意思是一样的。

↑ (API of UnionFind（Algorithms）)

1
2
3
4
5
6
7
8
// API of 61b

public interface DisjointSets {
    /** connects two items P and Q */
    void connect(int p, int q);

    /** checks to see if two items are connected */
    boolean isConnected(int p, int q); 
}

3. 模型范例

4. 用户如何使用API

II. Quick Find

1. 原理

用array的indice表示N个项目。
用array的value表示所属的set，用来判断是否连通（value相同的indice表明互相连通）。

2. 连通举例

假如我们要表示{0, 1, 2, 4}, {3, 5}, {6}，在quick find中会表现为：

此时，如果我们想连通2和3，id[2]=4, id[3]=5, quickfind方法会将所有value为4和5的元素统一为相同的value。

↑(所有value为4和5的元素都统一为5)

3. 复杂度

It takes N² array accesses to process a sequence of N union commands on N objects.

4. Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
public class QuickFindDS implements DisjointSets {

    private int[] id;

    /* Θ(N) */
    public QuickFindDS(int N){
        id = new int[N];
        for (int i = 0; i < N; i++){
            id[i] = i;
        }
    }

    /* need to iterate through the array => Θ(N) */
    public void connect(int p, int q){
        int pid = id[p];
        int qid = id[q];
        for (int i = 0; i < id.length; i++){
            if (id[i] == pid){
                id[i] = qid;
            }
        }
    }

    /* Θ(1) */
    public boolean isConnected(int p, int q){
        return (id[p] == id[q]);
    }
}

III. Quick Union

1. 原理

QuickFind每次连接的时候，需要改变多个value。有没有一个新的方法能使每次连接只改变一个value？

Idea：使用树形结构，每个index的value表示的是它连接的parant。若value为-1，则表示该index为最顶层。

2. 连通举例

此时，如果我们要连接index 5和index 2：connect(5, 2)

找到index 5的root: find(5) -> 3
找到index 2的root：find(2) -> 0
将index 5的root的值设置为index 2的root的值 -> parent[3]=0

这样就将两个需要连接的元素的root连接了起来，root下所有的元素也都连通了。

p10

3. 复杂度

p11

↑（假如tree的分支长度比较均衡，则quickunion比quickfind更快）

4. Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
public class QuickUnionDS implements DisjointSets {
    private int[] parent;

    public QuickUnionDS(int num) {
        parent = new int[num];
        for (int i = 0; i < num; i++) {
            parent[i] = i;
        }
    }

    private int find(int p) {
        while (parent[p] >= 0) {
            p = parent[p];
        }
        return p;
    }

    @Override
    public void connect(int p, int q) {
        int i = find(p);
        int j= find(q);
        parent[i] = j;
    }

    @Override
    public boolean isConnected(int p, int q) {
        return find(p) == find(q);
    }
}