并查集(Data Structure for Disjoint Sets)

为算法导论 v4 的 p520-545,p520-531 为算法内容本身,p531-541 为论证,p541-544 是题目,p544-545 则是章节笔记。

Disjoint Sets 的曾用名为 Union Find，二者指的都是一个东西。

这篇笔记主要是 p530-531 部分内容。

算法方面，Disjoint Sets 主要应用是 Minimum Spanning Tree 中的 Kruskal 算法，当然，其应用范围也就包括各种动态连接的问题。直接的应用不算多，但是使用 Disjoint Sets 为核心的拓展不少。

并查集操作

并查集的定义：

一个并查集维护一个由 $S=\{S_1, S_2, ..., S_n\}$ 集合组成的，动态不相连集
每一组集合中选出一个代表用以标识

在一些应用案例中，挑选代表需要花费一些额外的功夫，比如说挑选最大最小值等

每一个元素（set）都用一个对象 $x$ 来表示，并查集中主要有下面三个操作：

Make-Set( $x$ )

Make-Set 中的 $x$ 不能存在于其他任何集合中
Union( $x$ , $y$ )

集合两个不相关的，包括 $x$ 与 $y$ 的集合。

理论上来说，集合 $S_x$ 和 $S_y$ 应该会移除两个集合并创建一个新的 $S_x \bigcup S_y$ ，不过实际操作来说，基本会将一个集合并入到另一个集合中。
Find-Set( $x$ )

返回包含 $x$ 元素集合的代表指针。

书中提供了一个集合图的伪代码：

pseudo code

基本上这个就是并查集的基本逻辑。

上面的伪代码是以并查一个图为例，并查集最初表现为： ${a\}, \{b\}, \{c\}, \{d\}, \{e\}, \{f\}, \{g\}, \{h\}, \{i\}, \{j\}$ 10 个结点，边包括 $(b, d), (e, f), (a, c), (h, i), (a, b), (f, g), (b, c)$ 。

第一步先连接 $(b, d)$ ：

此时的并查集为： ${a\}, \{b, d\}, \{c\}, \{e\}, \{f\}, \{g\}, \{h\}, \{i\}, \{j\}$ 。集 ${b, d\}$ 中的代表应一致，这样 Find-Set(b) 与 Find-Set(d) 就会返回同样的结果。

第二步连接 $(e, f)$ ：

此时的并查集为： ${a\}, \{b, d\}, \{c\}, \{e, f\}, \{g\}, \{h\}, \{i\}, \{j\}$ 。同理集 ${e, f\}$ 中的代表也应一致。

第二步连接 $(a, c)$ ：

此时的并查集为： ${a, c\}, \{b, d\}, \{e, f\}, \{g\}, \{h\}, \{i\}, \{j\}$

以此类推，最终形成并查集如下：

可以看到通过并查集可以很方便的管理关联节点。

链表实现

链表是一个比较简单的实现方式，结点的是先参考如下：

class Node {
  this.head = null;
  this.value = null;

  constructor(value, head) {
    // initialize value
  }

  // setter and getters
}
1
2
3
4
5
6
7
8
9
10

通过链表的特性(链表是一个松散的数据结构，每次创建一个新的链表不需要修改原有链表的长度)以及包括了 head 和 tail 两个指针，Make-Set 与 Find-Set 两个函数的时间复杂度为 $O (1)$ ，单个 Union 操作的时间复杂度为 $O (n)$ 。

形象一点的理解就是参考下图：

最差条件下这个操作需要将 ${a,b,c,d,e,f,g\}$ 连到 $z$ 后面去，对于 ${a,b,c,d,e,f,g\}$ 的每个结点来说，都必须要更新 head 的指向，因此该操作的时间复杂度为 $O (n)$ ，也可以写成 $\theta(n)$ 。若两个链表的长度相等均为 $n$ ，最差条件下需要将两个链表的值全都遍历一遍更新 head 的指向，这个时间复杂度也为 $\theta(2n - 1)$ ，因此单个操作的时间上限为 $O (n)$ 。

增加权重的启发式

一个可以做的优化就是在 Union 的时候增加权重，即将短的链表增添至长链表的尾部，就可以将单词的操作时间从 $O (n)$ 优化到 $O(\log(n))$ 。

大概的证明就是，根据 增加权重的启发式 而言，每一次都合并长度较短的集，这也就代表了对于所有的集 $x$ 而言，第一次被更新时其原始长度为 $1$ ，被更新后其长度为 $2$ 。第二次集 $x$ 被更新时，其长度必然会 $\geq 4$ ——较短集的长度为 $2$ ，较长集的长度就必须 $\geq 2$ ，合并后的长度自然就 $\geq 4$ 。第三次集 $x$ 被更新时，其长度必然会 $\geq 8$ ，以此类推。

对于长度为 $n$ 的集而言，操作的上限就为 $ \log(n) $，时间复杂度的推演在二分算法原理及复杂度详解也有说，这里重新复述一遍好了：

$\frac{n}{4}, \frac{n}{2},..., n$
$\times (\frac{1}{2})^k = 1$
$\times \frac{1}{2^k} = 1$
$n = 2^k$
$\log(n)$

并查集森林

Disjoint Set Forest 是另外一种实现中常用的优化方式将 union 的时间复杂度压缩到 $\alpha(1)$ ，即均摊后时间复杂度为 $1$ 。根据书中所说，在实用案例中，Disjoint Set Forest 的时间复杂度增长不会超过 $4$ ，因此可以当作常数对待。

Disjoint Set Forest 使用的优化方式有两种：

Union By Rank

即根据权重进行合并，类似于链表中长度的计算
Path Compression

路径压缩是一个有效将搜索时间减少的方式，可以看到在链表实现中，每一次要寻找父结点时都需要经历一次长度为 $k$ 的迭代。路径压缩则是在每次调用 Find-Set() 的时候进行一个简单的判断，如果父元素的父元素与元素本身的父元素相同，则不做任何操作，否则就将元素的父元素指向父元素的父元素。

这么说起来比较绕口，图解看起来会简单一些，参考原本的链表格式：

经过路径压缩后：

可以看到 a --- f 的路径从原本的 5 步压缩到了一步，之后如果还需要寻找 f 的父元素，就可以直接返回 a 而不需要遍历整个 a --- f 这一段路径。

JavaScript 代码

这是按照书上的伪代码实现的，正确率已经用几道 LC 题测试过了，问题不大。

class UnionFind {
  constructor() {
    this.rank = {};
    this.parents = {};
  }

  makeSet(x) {
    this.parents[x] = x;
    this.rank[x] = 0;
  }

  findSet(x) {
    if (this.parents[x] !== this.parents[this.parents[x]]) {
      this.parents[x] = this.findSet(this.parents[this.parents[x]]);
    }

    return this.parents[x];
  }

  link(x, y) {
    if (this.rank[x] > this.rank[y]) {
      this.parents[y] = x;
    } else {
      this.parents[x] = y;
      if (this.rank[x] === this.rank[y]) {
        this.rank[y] = this.rank[y] + 1;
      }
    }
  }

  union(x, y) {
    this.link(this.findSet(x), this.findSet(y));
  }
}
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

相关阅读:
221.最大正方形
【教3妹学算法-每日3题(1)】检查单词是否为句中其他单词的前缀
Linux——基础指令
Flink学习8：数据的一致性
圆相交马蹄集
一起来学nginx(一)
SQL按月生成分区表，按月份查询该表数据
k8s--基础--22.12--storageclass--类型--Portworx 卷
[TI] [Textual Inversion] An image is worth an word
JVM整体结构

原文地址：https://blog.csdn.net/weixin_42938619/article/details/127711899