并查集 Disjoint-set

并查集（英文：Disjoint-set data structure，直译为不交集数据结构）是一种数据结构，用于处理一些不交集（Disjoint sets，一系列没有重复元素的集合）的合并及查询问题。如图的连通分量、拓扑网络的连通性之类的。并查集支持如下操作：

  1. 查询：查询某个元素属于哪个集合，通常是返回集合内的一个“代表元素”。这个操作是为了判断两个元素是否在同一个集合之中。
  2. 合并：将两个集合合并为一个。
  3. 添加：添加一个新集合，其中有一个新元素。添加操作不如查询和合并操作重要，常常被忽略。

由于支持查询和合并这两种操作，并查集在英文中也被称为联合-查找数据结构（Union-find data structure）或者合并-查找集合（Merge-find set）。

“并查集”可以用来指代任何支持上述操作的数据结构，但是一般来说，“并查集”特指其中最常见的一种实现：不交集森林（Disjoint-set forest）。经过优化的不交集森林有线性的空间复杂度O(n)O(n), nn为元素数目，下同），以及接近常数的单次操作平均时间复杂度O(α(n))O(α(n))， αα为反阿克曼函数），是效率最高的常见数据结构之一。

实现

并查集的实现通常是一个单数组，数组的每个元素记录自己的父节点索引。因此，初始化的时候需要把每个元素的值赋值为自己的索引，如[1,2,3,4..]。不难发现这是树形结构的集合。

合并

合并操作即把两个集合进行合并，即把两棵树的根节点进行合并，因为根节点记录的索引肯定是指向自己的，因此简单的把索引指向合并的另一个树的根节点即可。

查询

查询返回该节点所在树的根节点，一直往上递归到根节点并返回即可。

调优

路径压缩

由于合并时是随意的指向两棵树的任意一个根节点，可能会导致树越来越高，退化成链表。因此可以在查询的时候将路径上的所有点的父节点设置为根节点。

按秩合并

合并时是随意的指向两棵树的任意一个根节点，因为新的父节点的增加，所以被合并的那个树的高度肯定会增加1。为此可以初始一个 rank，默认都是 1，有别的树合并进来便把新的根节点的rank+1。这里的 rank 并不是高度，也不是节点数，而是被合并的次数，被合并的次数越多，子节点就越多，高度+1 后的所有子节点的路径+1 就越不利。因此，rank低的往rank高的合并是合理的。

算法模板

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
class DisJointSet {
    constructor(n) {
        this.f = [...Array(n).keys()]
        this.rank = Array(n).fill(1) // 按秩合并
    }
    get Connected() { // 可以理解是寻找所有连通分量（即自己是自己的父节点）
        return this.f.filter((x, i) => x === i)
    }
    find(x) { // 返回树的根节点
        return x === this.f[x] ? this.f[x] : (this.f[x] = this.find(this.f[x])) // this.f[x] = this.find(this.f[x])路径压缩
    }
    union(x, y) { // 合并两个树
        const rootX = this.find(x)
        const rootY = this.find(y)
        if (rootX === rootY) {
            // 要合并的两个节点属于同一个集合，无需合并（合并虽然不会出错但是可能会影响秩的准确性）
            return
        }
        if (this.rank[rootX] > this.rank[rootY]) {// rootX比较深
            this.f[rootY] = rootX
        } else if (this.rank[rootX] < this.rank[rootY]) { // rootY比较深
            this.f[rootX] = rootY
        } else {//一样深就随便，深度加1
            this.f[rootX] = rootY
            this.rank[rootY]++
        }
    }
}

扩展

Kruskal’s algorithm (克鲁斯克尔算法)

封面图就是克鲁斯克尔算法，是一种用来查找最小生成树的算法

美国数学家约瑟夫·克鲁斯克尔在 1956 年发表了该算法，用于查找图的最小生成树。最小生成树（Minimum spanning tree，简称 MST）即在连通加权无向图中一棵权值最小的生成树。可以用于规划城市的道路建设之类的（总体造价最低）。

那算法是怎么运行的呢？其实很简单

  1. 初始化一个并查集
  2. 把所有边按权值排序
  3. 从小往大的遍历排序结果（可以看出是贪心算法了），如果当前遍历的边的两个端点不连通在1.的并查集内，则将两个端点合并，并记录 MST

记录完收工

2024-05-28

一道比较好的并差集题目：
399. 除法求值

示例 1：
输入：equations = [[“a”,”b”],[“b”,”c”]], values = [2.0,3.0], queries = [[“a”,”c”],[“b”,”a”],[“a”,”e”],[“a”,”a”],[“x”,”x”]]
输出：[6.00000,0.50000,-1.00000,1.00000,-1.00000]
解释：
条件：a / b = 2.0, b / c = 3.0
问题：a / c = ?, b / a = ?, a / e = ?, a / a = ?, x / x = ?
结果：[6.0, 0.5, -1.0, 1.0, -1.0 ]
注意：x 是未定义的 => -1.0

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
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
/**
 * @param {string[][]} equations
 * @param {number[]} values
 * @param {string[][]} queries
 * @return {number[]}
 */
var calcEquation = function (equations, values, queries) {
    const s = new DisJointSet(equations, values), ans = []
    for (let [x, y] of queries) {
        if (s.map[x] > -1 && s.map[y] > -1) {
            let rx = s.find(s.map[x])
            let ry = s.find(s.map[y])
            if (rx[0] == ry[0]) {
                ans.push(s.f[s.map[y]][1] / s.f[s.map[x]][1])
            } else {
                ans.push(-1.0)
            }
        } else {
            ans.push(-1.0)
        }
    }
    return ans
};
class DisJointSet {
    constructor(equations, values) {
        this.map = {}
        this.f = []
        const child = new Set()
        for (let i of _.range(equations.length)) {
            const [x, y] = equations[i]
            if (!(this.map[x] > -1)) {
                this.map[x] = this.f.length
                this.f.push([this.map[x], 1])
            }
            if (!(this.map[y] > -1)) {
                this.map[y] = this.f.length
                this.f.push([this.map[y], 1])
            }
        }
        // console.log('before_union', this, equations)
        for (let i of _.range(equations.length)) {
            this.union(...equations[i], values[i])
        }
        // console.log('union', this)
    }

    find(i) {
        if (i == this.f[i][0]) {
            return this.f[i]
        } else {
            const tar = this.find(this.f[i][0])
            this.f[i] = [tar[0], tar[1] * this.f[i][1]]
            return this.f[i]
        }
    }

    // b->a
    union(a, b, scale) {
        let rootI = this.find(this.map[a])
        let rootJ = this.find(this.map[b])
        // 无环
        if (rootI[0] !== rootJ[0]) {
            // 先改权值，不然引用出错
            this.f[rootJ[0]][1] = scale * this.f[this.map[a]][1] / this.f[this.map[b]][1] // 这里的可以直接运算的原因是做了路径压缩
            // 更新父节点
            this.f[rootJ[0]][0] = rootI[0]
        }
    }
}