Union-Find算法

发表于 | 分类于 | 阅读次数:
字数统计: 2,199 | 阅读时长 ≈ 9

并查集是一种数据结构，而union-find算法定义了用于此数据结构的操作。这是维基给的简单定义，而这篇笔记主要是针对《算法》这本书上出现的相关问题，暂且不深入展开这个定义。

准备工作

在《算法》这本书中，列举出union-find算法的API有以下这些：

1
UF(int N)

这是一个初始化类的构造器。

1
void union(int p, int q)

表示对输入的两个点进行连接。

1
int find(int p)

表示该点所在分量的标识符（分量名）。

1
boolean connected(int p, int q)

判断两个点是否连接。

1
int count()

分量的个数。

算法的优劣，主要决定于find()和union()这两个函数，所以下面给出书中暂时没有实现find()和union()的UF类的代码：

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
public class UF {
  private int[] id;
  private int count;
  public UF(int N) {
    count = N;
    id = new int[N];
    for (int i = 0; i < N; i++) {
      id[i] = i;
    }
  }
  public int count() {
    return count;
  }
  public boolean connected(int p, int q) {
    return find(p) == find(q);
  }
  public int find(int p) {
    // 未实现
  }
  public void union(int p, int q) {
    //未实现
  }
  public static void main(String args[]) {
    int N = StdIn.readInt();
    UF uf = new UF(N);
    while (!StdIn.isEmpty()) {
      int p = StdIn.readInt();
      int q = StdIn.readInt();
      if (uf.connected(p, q)) continue;
      uf.union(p, q);
      StdOut.println(p + " " + q);
    }
    StdOut.println(uf.count() + "components");
  }
}

注：代码用到了本书作者自己编写的函数库，比如StdIn.readInt()基本上就是封装了scanner.nextInt()等，为了方便和兼容，这里就使用原书的代码。

UF的构造很容易理解，最初将所有点当作单个的联通分量，然后每个联通分量有一个自己的分量名id，通过find()可以找到当前输入点所属的分量名，而union()就是不断通过所给输入条件合并已知分量。

quick-find

由于算法的优劣，主要决定于find()和union()这两个函数，首先考虑对find()进行优化。

find()操作速度很快的一种情况是，通过给出的点(假设为p)，立马就可以得到p所属的分量名，以下代码就可以满足：

1
2
3
public int find(int p) {
  return id[p];
}

数组id[]直接存储各个点所属的分量名，每次调用find()只访问一次数组。

注：访问一次数组指的是通过数组名[索引](这里指的是id[p])进行的一次操作，认识这一点方便后面的算法分析。

由于每个点p调用id[p]就能得到它所在的分量名，那么当输入两个点p, q，如果find(p)和find(q)相等，就说明它们在同一个分量，不需要采取动作；当不等的时候，就把和其中一个点拥有相同分量名的所有点的id改为另一个点的分量名。实现如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public void union(int p, int q) {
  int pID = find(p);
  int qID = find(q);
  if (pID == qID)
    return;
  for (int i = 0; i < id.length, i++) {
    if (id[i] == pID) {
      id[i] = qID;
    }
  }
  count--;
}

书中说union()访问数组的次数在N+3到2N＋1之间。只要理解了成本模型，就能得出这个结果。

在本算法中，成本模型是数组的访问次数，而每进行一次id[p]的操作就会访问一次数组。所以int pID = find(p)和int qID = find(q)进行了两次数组访问，if (pID == qID) return;没有进行数组访问，接下来的for循环中if (id[i] == pID)进行了N次判断，每一次都会进行一次id[]操作，id[i] = qID;的执行分最好最坏两种情形，最好的情形是，p是孤立的一个分量，于是只需要访问一次id[i]就可以了(2+N+1=N+3)；最坏的情形是，p所在的分量有N-1个点，这时候要访问并修改N-1个id[]的元素的值(2+N+N-1=2N+1)。

注：虽然循环中经过编译的代码对id[p]的第二次引用一般不会访问数组，但是在这个算法中第二次是会修改元素值的，所以是会访问数组的。

由于调用union()的次数是线性级别的(0到N-1)，所以quick-find算法的时间复杂度是平方级别的。

quick-union

如果说quick-find算法是把“查找”的过程放在了union()(这里指代其中的for语句)，那么quick-union算法就是把“查找”丢给了find()函数。

要理解quick-union算法，首先要知道它约定的“游戏规则”，这个“游戏规则”适合用类似迭代的方法说明：

首先，假设有两个点p和q，它们分别是独立的分量，分量名分别是id[p]和id[q]，如果要求构造p和q的连接，则有两种情况，一种是将id[p]更改为q的分量名id[q]，这个过程好似q成为了p的父节点；另一种是将id[q]更改为q的分量名id[p]，这个过程好似p成为了q的父节点。

现在新增加一个点m，此点如果构造为与刚刚p，q组成的分量相连，则构造方法有两种，一种是将id[m]设为p，q分量的根节点，此时好似把m点的父节点设为p，q分量的根节点；一种是将id[p，q分量的根节点]设为id[m]，好似把p，q分量根节点的父节点设为m，如图所示(这里假定q是p，q分量的根节点)：

图1

经过多次迭代，现假设有两个分量A，B，每个分量都包含多个节点，如果要求构造两个分量相连，则构造方法同样有两种，一种是将A分量根节点的父节点设置为B的根节点，另一种则相反。

find()代码就是寻找每个分量根节点的函数：

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

而“游戏规则”可以通过union()来描述：

1
2
3
4
5
6
7
8
9
10
11
public void union(int p, int q) {
  int pRoot = find(p);
  int qRoot = find(q);
  if (pRoot == qRoot) {
    return;
  }
  id[pRoot] = qRoot;
  count--;
}

由前述的“游戏规则”可知，代码id[pRoot] = qRoot;是根据输入点的顺序而采用的构造相连方法的两种中的一种，所以整个构造过程有可能出现最坏的情况，例如每次构造单点分量与多点分量相连，单点分量都设置成多点分量根节点的父节点。find()可能进行2N+1次数组访问(树中节点深度的两倍加1)。

注：find()函数中while部分经过编译的代码对id[p]的第二次引用一般不会访问数组。

加权quick-union & 路径压缩加权quick-union

前面已经提到了，代码id[pRoot] = qRoot;是根据输入点的顺序而采用的构造相连方法的两种中的一种，加权quick-union就是来规避这种随输入的选取造成的整个算法出现最坏情况的问题。

在前述“游戏规则”中，A，B两个多点分量的连接过程中，只要保证其中较小的树连接到较大的树，最坏情况就不会出现，具体的实现方法是增加一个数组专门用来记录一个分量的大小：

1
2
3
4
int[] sz = new int[N];
  for (int i = 0; i < N; i++) {
    sz[i] = 1;
  }

首先初始化一个数组，每个元素设为1。

将union()作相应更改：

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

路径压缩则是对加权quick-union算法的再优化，在quick-find算法中，find之所以快是因为，每个节点的分量名只要访问一次数组id[]就可以得到，如果多点分量中每个节点都直接链接到同一个父节点，就可以将算法无限接近与quick-find的效果。

改进find()：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
private int find(int p) {
  int r, n, t;
  r = p;
  n = p;
  while (r != id[r]) {
    r = id[r];
  }
  while (n != r) {
    t = id[n];
    id[n] = r;
    n = t;
  }
  return r;
}

添加的部分是将p节点路径上节点的父节点全部设置为分量的根节点。

注：知乎上有一个递归的解法：

1
2
3
int find(int x){
        return x==id[x]?x:id[x]=find(id[x]);
}

总结

本笔记按照书中的流程复习了union-find算法，并增加了如下几个工作：

  1. 分析了为什么书中quick-find算法的union()函数访问数组的次数在N+3到2N+1之间；
  2. 用自己的语言描述了quick-union算法的构造过程；
  3. 添加了书中没有实现的路径压缩加权quick-union算法；