并查集拓展

并查集的实现里面有提到,并查集两种实现方式:

  • 一种是使用数组,索引作为元素,数组值作为集合,这种方式适合快速查询。
  • 一种是基于森林实现,不过也是使用数组结构,索引作为元素,数组值存储其父节点的方式。

在一般使用并查集的场景中,基本上都是采用第二种,基于森林的实现方式。

不过在真实业务场景中,元素可能不仅仅是数字类型,也有可能是字符串类型,或者对象类型。

所以,在实现上,需要换一种结构实现。

基于哈希表实现

如果元素是字符串或对象类型,我们可以直接使用Map代替数组来实现查并集。

其中元素作为Map的键key,而其所属的集合名作为Map的value值。

初始情况下,元素的所属集合(即parent节点)为自己。

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
class UnionFindSet {
constructor(names) {
this.nameMap = new Map();
if (names) {
for (const name of names) {
this.nameMap.set(name, name);
}
}

}
// 查找元素,属于哪个集合
find(name) {
let root = this.nameMap.get(name);
while (root && root != this.nameMap.get(root)) {
root = this.nameMap.get(root);
}
return root;
}
// 添加元素
add(name) {
let root = this.find(name);
if (!root) {
this.nameMap.set(name, name);
root = name;
}
return root;
}
// 合并操作,将集合x和集合y合并成一个集合
union(x, y) {
const rootX = this.add(x);
const rootY = this.add(y);
if (rootX == rootY) {
return false;
}
if (rootX < rootY) {
this.nameMap.set(rootY, rootX);
} else {
this.nameMap.set(rootX, rootY);
}

return true;
}

// 查询操作:判断x和y是否同属于 一个集合
isConnected(x, y) {
return this.find(x) == this.find(y);
}
}

基于对象节点

由于并查集是一个树的结构,因此,我们可以采用对象节点的方式来实现,就像实现二叉树一样,定义一个节点对象,然后通过parent指针指向其父节点,一次来达到树的节点引用。

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
class ItemNode {
constructor(val) {
this.val = val;
// 初始情况下,parent指向自己
this.parent = this;
}
}
class UnionFindSet {
constructor(names) {
this.map = new Map();
if (names) {
for (const name of names) {
const node = new ItemNode(name);
this.map.set(name, node);
}
}

}
// 查找元素,属于哪个集合
find(name) {
let node = this.map.get(name);
while (node && node != node.parent) {
node = node.parent;
}
return node;
}
add(name) {
let root = this.find(name);
if (!root) {
const node = new ItemNode(name);
this.map.set(name, node);
root = node;
}
return root;
}
// 合并操作,将集合x和集合y合并成一个集合
union(x, y) {
const rootX = this.add(x);
const rootY = this.add(y);
if (rootX == rootY) {
return false;
}
if (rootX.val < rootY.val) {
rootY.parent = rootX;
} else {
rootX.parent = rootY;
}

return true;
}

// 查询操作:判断x和y是否同属于 一个集合
isConnected(x, y) {
return this.find(x) == this.find(y);
}
}

此两种实现方式,在使用上可能更具通用性,不管要处理的数据类型是什么,都可以应对。