并查集算法分析

并查集算法是用于判断互联网中我们是否需要新建立一条连接来使整个网络连通。即,元素的连通性问题。

1. 概念

  • 连接

    连接是一种等价关系,它意味着以下特点:

    • 自反性:pp 连接着 pp
    • 对称性:如果 ppqq 相连,那么 qqpp 相连
    • 传递性:如果 ppqq 相连,qqrr 相连,那么 pprr 相连

2. Union-Find 的实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public static void main(String[] args) {
int N = StdIn.readInt(); //read the Number of CONTACTS
UF UF = new UF(N); //Initialize the data structure

while(!StdIn.isEmpty()) {
int p = StdIn.readInt();
int q = StdIn.readInt();

if(uf.connected(p,q)) {
//If it is connected, ignore it
continue;
}

uf.uinon(p,q); //Merge the contacts
StdOut.println(p + " " + q);
}
}

3. union()find() 的实现

基于 id[] 数组,他们的每一个索引都是一个节点

3.1 Quick-Find 算法

这是一个 naive 的实现,每次执行 union() 都需要扫描整个数组。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public int find (int p) {
return id[p];
}

public void union(int p, int q) {
// Merge p and q into the same component
int pID = find(p);
int qID = find(q);

// If the p and q are at the same component,
// do nothing and return.
if(pID = qID) {
retrun;
}

// Rename the p component to the q component
for(int i = 0; i< id.lenth; i++) {
if(id[i] == pID) {
id[i] = qID;
}
}
count --; // Decrease the component counter
}

connected() 方法需要 2 次 find();而对于 union() 方法则需要调用两次 find() ,检查 NN 个数组元素,改变其中 1N11 \sim N - 1 个数组元素的值。

所以,执行一次 connected()union() 需要 N+32N+1N+3 \sim 2N + 1 数组访问。

而如果最后仅得到一个连通分量,那么就需要进行 N1N - 1connected() + union(),也就是至少需要 (N+3)(N1)N2(N + 3)(N - 1) \sim N^2 次数组访问。

3.2 Quick-Union 算法

使用作为基本结构以避免每次调用 union() 时,都要扫描整个数组

3.2.1 基本概念

  1. 使用树作为基本的数据结构

  2. 每一个节点的 id[] 元素就是另一个节点的名字,我们认为它们之间建立了一个连接

    例如, ppqq 是两个节点,如果 ppqq 连接,那么 id[p] == q

  3. 如果 id[p] == p,那么我们称 pp 是一个根节点

3.2.2 实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
private int find(int p) {
// Find the root of the contact's component
while (p != id[p]) {
p = id[p];
}
return p;
}

public void union(int p, int q) {
// Merge the root contact of the p's component and the q's component
int pRoot = find(p);
int qRoot = find(q);

// If the two components' root are the same, return.
if (pRoot == qRoot) {
return;
}

// Set the p's tree links with q's tree.
// Now, the qRoot is the father contact of the qRoot.
id[pRoot] = qRoot;

count --;
}

3.3.3 性能

虽然一般来说,并查集算法比 Quick-Find 算法要快,但是在最坏情况下,并查集算法仍然需要 2(1+2++N)N22(1 + 2 + \ldots + N) \sim N^2 次的数组访问

原因在于, union() 方法是随机的连接两棵树,就有可能将大树连接到小树上,增加树的深度。

如果所有的树都是大树连接到小树上,那么树就变成了线性表,此时即为最坏情况。

4. 加权的并查集算法

我们通过给树增加权值,从而可以避免上面的随机连接的情况。
权值即为树的大小。

4.1 实现

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
30
31
32
33
34
35
36
37
38
39
40
41
public class WeightedQuickUnionUF {

/**
* We need a new array to count the tree's size
* The index is the root contact
* The value is the corresponding size of the tree

* Baically, we use the root contact to stand for the tree
*/
private int[] sz;
....
public WeightedQuickUnionUF (int N) {
...
sz = new int[N];
for (int i = 0; i < N; i++) {
// Initialize the sz[] as 1.
// No one was linked at the first.
sz[i] = 1;
}
}
...
public int find(int p) {
// Find the root contact
while (p != id[p]) {
p = id[p];
}
retrun p;
}

public void union(int p, int q) {
...
if (sz[i] < sz[j]) { // Link the smaller tree's root contact to the bigger one
id[i] = j;
sz[j] += sz[i]; // Adding the weight(or size) of the component
}
else {
id[j] = i;
sz[i] += sz[j];
}
}
}

4.2 性能

通过使用加权算法,构造的森林中,任意节点的深度最多为 logNlogN [1]

5. 路径压缩的并查集算法

更进一步,我们可以在遍历到一个节点的时候,就和它的根节点连在一起,
由于我们只检查连通分量(即根节点)是否相连,所以上述做法在 Union-Find 问题中是没有副作用的,同时可以极大地减少树的深度,从而提升算法性能。

5.1 实现 1 ——两个循环

使用第二个循环,将寻找根节点路径上的所有的点都与根节点直接连接。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public int find(int p) {
int pParent = p;
int pRoot = p;

// Find the p's root
while(pRoot != id[pRoot]) {
pRoot = id[pRoot];
}

while (id[p] != p) {
pParent = id[p];
id[p] = pRoot;
p = pParent;
}

return pRoot;
}

5.2 实现 2 ——将点指向其爷爷节点

一个更为简单的实现,直接将节点与其爷爷节点连接即可;

虽然效果没有 实现 1 好,但是在实际运用中,两者效果相差不大,而且实现 2 只需要一行代码即可,更具备工程意义。

1
2
3
4
5
6
public int find(int p) {
while(p != id[p]) {
id[p] = id[id[p]];
p = id[p];
}
}

5.3 性能

这个算法的性能是一个 arcarc 函数,十分接近常数

6. 比较

The comparation of the Union-Find algorithm


  1. 在算法中 logNlogNlog2Nlog_2{N} 等价 ↩︎