UnionSearch [合并搜索]
# 介绍
# 并查集
在计算机科学中，并查集（英文：Disjoint-set data structure，直译为不交集数据结构）是一种数据结构，用于处理一些不交集（Disjoint sets，一系列没有重复元素的集合）的合并及查询问题。并查集支持如下操作：
查询：查询某个元素属于哪个集合，通常是返回集合内的一个 “代表元素”。这个操作是为了判断两个元素是否在同一个集合之中。 合并：将两个集合合并为一个。 添加：添加一个新集合，其中有一个新元素。添加操作不如查询和合并操作重要，常常被忽略。 由于支持查询和合并这两种操作，并查集在英文中也被称为联合 - 查找数据结构（Union-find data structure）或者合并 - 查找集合（Merge-find set）。
# Union Find
Union Find 算法用于处理 集合的合并和查询 问题，其定义了两个用于并查集的操作：
Find: 确定元素属于哪一个子集，判断两个元素是否属于同一子集（即，查找元素的 root，当两元素 root 相同时判定他们属于同一个子集）。Union: 将两个子集合并为一个子集（即通过修改元素的 root 或 parent 来合并子集）。
并查集是一种树形的数据结构，其可用数组或 unordered_map 表示，下面这个图很清晰的展示了并、查、集。摘自 UnionFind Algorithm (opens new window)。
# 伪代码
构造函数必须传入参数 n，即，已知 set 里面最多会有 n 个元素。
每个元素（节点）都有一个 parent，假设最开始每个节点的 parent 都是其自身（1~n），也就是一个个独立的 cluster。相应的，rank 全部初始化为 0。
我们定义两个 function：Find 和 Union。Find 作用是返回节点 x 的根节点，根节点就是从 x 往上沿着 parent 的路径一直找，直到某个节点它的 parent 就是自身，那么这个节点就是根节点。在 Find 的过程中顺便做了 path compression，也就是递归调用 Find 函数，对于沿途每个 parent 节点都执行 Find 来寻找它们的根节点，最终根节点逐级向下传递到，这些之前的所有 parent 节点也都会指向根节点。
# 实现
# JavaScript
/**
* union find data structure for javascript
*
* In computer science, a disjoint-set【并查集】 data structure, also called a union–find data structure or merge–find set,
* is a data structure that stores a collection of disjoint (non-overlapping) sets. Equivalently, it stores a partition
* of a set into disjoint subsets. It provides operations for adding new sets, merging sets (replacing them by their union),
* and finding a representative member of a set.
* The last operation allows to find out efficiently if any two elements are in the same or different sets.
*
* Disjoint-set data structures play a key role in Kruskal's algorithm for finding the minimum spanning tree of a graph.
* The importance of minimum spanning trees means that disjoint-set data structures underlie a wide variety of algorithms.
* In addition, disjoint-set data structures also have applications to symbolic computation, as well in compilers,
* especially for register allocation problems.
*
* you can learn more on disjoint-set / union–find data structure at https://en.wikipedia.org/wiki/Disjoint-set_data_structure
*/
function UnionSearch (n, key) {
if (!(this instanceof UnionSearch)) return new UnionSearch(n)
if (key && typeof key !== 'function') {
throw new Error('key has to be a function or else left undefined')
}
let cnt, length
// init Union Find with number of distinct groups. Each group will be referred to as index of the array of size 'size' starting at 0.
// Provide an optional key function that maps these indices. I.e. for the groups starting with 1 provide function(a){return a-1;}. The default value is function(a){return a;}.
key = key || function (a) { return a }
cnt = length = n
const id = new Array(n)
const sz = new Array(n)
for (let i = 0; i < n; i++) {
id[i] = i
sz[i] = 1
}
// Returns the number of elements of uf object.
this.size = function () {
return length
}
// Returns the number of distinct groups left inside the object.
this.count = function () {
return cnt
}
// Return the root (value) of the group in which p is.
this.find = function (p) {
p = key(p)
while (p !== id[p]) {
id[p] = id[id[p]]
p = id[p]
}
return p
}
// Returns true if p and p are both in same group, false otherwise.
this.connected = function (p, q) {
p = key(p)
q = key(q)
ensureIndexWithinBounds(p, q)
return this.find(p) === this.find(q)
}
// Combine elements in groups p and q into a single group. In other words connect the two groups.
this.union = function (p, q) {
p = key(p)
q = key(q)
ensureIndexWithinBounds(p, q)
const i = this.find(p)
const j = this.find(q)
if (i === j) return
if (sz[i] < sz[j]) {
id[i] = j; sz[j] += sz[i]
} else {
id[j] = i; sz[i] += sz[j]
}
cnt--
}
function ensureIndexWithinBounds (args) {
for (let i = arguments.length - 1; i >= 0; i--) {
const p = arguments[i]
if (p >= length) throw new Error('Index out of bounds. The maximum index can be length-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
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
70
71
72
73
74
75
76
77
78
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
70
71
72
73
74
75
76
77
78
# Python
class UnionFindSet:
def __init__(self, n):
self._parents = [i for i in range(n + 1)]
self._ranks = [1 for i in range(n + 1)]
def find(self, u):
while u != self._parents[u]:
self._parents[u] = self._parents[self._parents[u]]
u = self._parents[u]
return u
def union(self, u, v):
pu, pv = self.find(u), self.find(v)
if pu == pv: return False
if self._ranks[pu] < self._ranks[pv]:
self._parents[pu] = pv
elif self._ranks[pu] > self._ranks[pv]:
self._parents[pv] = pu
else:
self._parents[pv] = pu
self._ranks[pu] += 1
return True
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
# 参考
编辑 (opens new window)
上次更新: 2022/06/20, 20:15:04