盒子
盒子
文章目录
  1. Nim编程早茶
    1. 初始化
    2. quick-find
    3. 加权合并
    4. 测试程序

Nim 语言实现加权并查集

Nim编程早茶

并查集,可以用于快速判断两个元素是否在同一个集合中;也可以快速将两个集合合并。而加权并查集,可以以 logN 的时间复杂度查找与合并集合。

初始化

并查集的 data 属性由一维整型数组构成,每个数值都属于一个集合。比如 data 的大小为 10,初始的时候,就有 10 个不同的集合。每一个元素的数值,代表该元素父节点在数组中的位置。顺着父节点,我们可以找到元素的根节点,而这个根节点决定了这个元素所属的集合。初始时,每个元素的根节点就是自身,也说明刚开始的时候,每个元素都属于不同的集合。

size 集合也是同样大小的一维整型数组,每个元素,代表 data 中对应位置元素所属的集合中元素的个数。比如说size[3] = 3,就说明 data[3] 所属的集合的大小为 3。

count 属性表示,并查集中,尚未连接的集合个数。刚开始的时候,count 等于 len(data)。如果最终各个集合合并成一个集合之后, count 就变为 1。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
type
WeightedUnionSet*[N: static[int]] = object
data*: array[N, int]
size*: array[N, int]
# 连通分量的个数
count: int

proc newWeightedUnionSet*[N: static[int]](): WeightedUnionSet[N] =
result.count = N
for i in 0 ..< N:
result.data[i] = i
result.size[i] = 1

proc count*(w: WeightedUnionSet): int =
w.count

quick-find

find 函数用来递归地寻找元素的根节点。当 data[p]=p 的时候,就说明找到了根节点。

1
2
3
4
5
6
7
8
9
10
proc find*(w: WeightedUnionSet;p: int): int = 
var p = p
while w.data[p] != p:
p = w.data[p]
return p

# 判断两个元素时候是否在同一个集合中
# 只需要判断两个元素的根节点是否相同
proc connected*(w: WeightedUnionSet;p, q: int): bool =
find(w, p) == find(w, q)

加权合并

首先,我们找到 p, q 元素的根节点。如果他们在同一个集合中,我们就返回。

否则,我们需要合并这两个集合。合并的时候,需要比较两个集合中元素的个数,我们把小集合并到大集合中。只需将小集合的根节点指向大集合的根节点,也就是让 data[small]=large,然后增加大集合元素的个数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
proc union*(w:var WeightedUnionSet;p, q: int) =
let
i = find(w, p)
j = find(w, q)
if i == j: return
if w.size[i] < w.size[j]:
w.data[i] = j
w.size[j] += w.size[i]
else:
w.data[j] = i
w.size[i] += w.size[j]
w.count -= 1

proc `$`(w: WeightedUnionSet): string =
$w.data

测试程序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
when isMainModule:
var w = newWeightedUnionSet[10]()
w.union(4, 3)
w.union(3, 8)
w.union(6, 5)
w.union(9, 4)
w.union(2, 1)
w.union(8, 9)
w.union(5, 0)
w.union(7, 2)
w.union(6, 1)
w.union(1, 0)
w.union(6, 7)
echo w

输出

1
[6, 2, 6, 4, 4, 6, 6, 2, 4, 4]