RUOCHI.AI
0%

Union Find

Posted on Edited on In Valine:
Union Find

定义

并查集是一种树型的数据结构，用于处理一些不相交集合的合并及查询问题。常常在使用中以森林来表示。并查集有三种基本操作，获得根节点，判断两节点是否连通，以及将两不连通的节点相连（相当于将两节点各自的集合合并）。

实现

用UnionFind类来表示一个并查集，在构造函数中，初始化一个数组parent，parent[i]表示的含义为，索引为i的节点，它的直接父节点为parent[i]。初始化时各个节点都不相连，因此初始化parent[i]=i，让自己成为自己的父节点，从而实现各节点不互连。

1
2
def __init__(self, n):
    self.parent = list(range(n))

由于parent[i]仅表示自己的直接父节点，查询两个节点是否相交需要比较它们的根节点是否相同。因此要封装一个查询自己根节点的方法。

1
2
3
4
def get_root(self, i):
   while i != self.parent[i]:
       i = self.parent[i]
   return i

接下来可以通过来比较根节点是否相同来判断两节点是否连通。

1
2
def is_connected(self, i, j):
    return self.get_root(i) == self.get_root(j)

当要连通两个节点时，我们要将其中一个节点的根节点的parent，设置为另一个节点的根节点。注意，连通两个节点并非仅仅让两节点自身相连，实际上是让它们所属的集合实现合并。

1
2
3
4
5
def union(self, i, j):
    i_root = self.get_root(i)
    j_root = self.get_root(j)
    if i_root != j_root:
        self.parent[i_root] = j_root

优化

由于调用get_root时需要通过不断找自己的直接父节点，来寻找根节点，如果这棵树的层级过深，会导致性能受到严重影响。因此我们需要在union时，尽可能的减小合并后的树的高度。在构造函数中新建一个数组rank，rank[i]表示节点i所在的集合的树的高度。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def __init__(self, n):
    self.parent = list(range(n))
    self.rank = [0] * len(self.parent)


def union(self, i, j):
    i_root = self.get_root(i)
    j_root = self.get_root(j)

    if self.rank[i_root] == self.rank[j_root]:
        self.parent[i_root] = j_root
        self.rank[j_root] += 1
    elif self.rank[i_root] > self.rank[j_root]:
        self.parent[j_root] = i_root
    else:
        self.parent[i_root] = j_root

通过对union操作的改良可以防止树的高度过高。我们还可以对get_root操作本身进行优化。 当前每次执行get_root时，需要一层一层的找到自己的父节点，很费时。由于根节点没有父节点，并且文章开始处提到过如果一个节点没有父节点，那么它的父节点就是自己，因此可以说只有根节点的父节点是自己本身。现在我们加上一个判断，判断当前节点的父节点是否为根节点，如果不为根节点，就递归地将自己的父节点设置为根节点，最后返回自己的父节点。

1
2
3
4
def get_root(self, i):
    if self.parent[i] != self.parent[self.parent[i]]:
        self.parent[i] = self.get_root(self.parent[i])
    return self.parent[i]