数据结构: 并查集
引入
并查集 (Disjoint Sets) 是一种用于高效管理不相交集合的数据结构，常用于处理动态连通性问题，例如判断两个元素是否属于同一集合、合并集合等。
并查集支持以下三种基本操作:
- 初始化 (MakeSet): 为每个元素创建一个独立集合。
- 查找 (Find): 查找某个元素所属集合的代表 (根节点)。
- 合并 (Union): 将两个元素所在的集合合并为一个。
并查集无法以较低复杂度实现集合的分离。
接下来我们介绍并查集的基础实现和进阶实现。
基础实现
基础实现只需维护一个parent数组。
初始化
初始时, 每个元素都位于一个单独的集合, 表示为一棵只有根节点的树。如果一开始有n个元素, 那我们就创建长度为n的parent数组, 并且parent[i] = i。
在并查集的实现中为了方便一般将根节点的父亲设为自己。
def __init__(self, n): self.parent = list(range(n))查找
查找某个元素属于哪个集合, 这个问题放到树中就是从这个节点就是不断向上, 直到找到根节点。 为了减少后续查找时向上寻找的开销, 可以在查找过程中进行路径压缩, 降低树的高度。 具体来说, 首先沿着节点不断向上, 找到根节点, 然后再将路径上的所有节点的父亲设为根节点。
def find(self, x): old = x ancestor = parent[x] while ancestor != x: x = ancestor ancestor = parent[x] x = parent[old] while ancestor != x: parent[old] = ancestor old = x x = parent[x] return ancestor合并
合并两个不相交的集合, 统一选择将左边树的根节点连到右边树的根节点。
def union(self, x, y): rootX = self.find(x) rootY = self.find(y) if rootX != rootY: self.parent[rootX] = rootY # 合并集合
进阶实现
在基础版合并的实现中, 我们固定将右侧的树的根节点作为新树的根节点, 这并不合理。 如果左边的树更大, 那么就会有更大概率会多向上访问一次, 在上面的例子中, 左树有 5 个节点, 而右树有 3 个节点, 将右树的根作为新树的根节点会导致我们有 的节点在查找时需要多向上访问一次。 那么看来如果某一边的树更大 (节点数更多), 更适合选择其根节点作为新树的根节点。
一般的做法是追踪树的深度, 而不是追踪树的节点数, 我们要引入rank数组, 表示树的高度, 这个方法叫按秩分配。
初始化
初始时, 每个树的高度为 0。
def __init__(self, n): self.parent = list(range(n)) self.rank = [0] * n查找
依然是带路径压缩的查找, 但是使用的是更加优雅的递归式写法。
def find(self, x): if self.parent[x] != x: self.parent[x] = self.find(self.parent[x]) return self.parent[x]合并
根据rank绝对选择哪个树的根节点作为新树的根节点, 当两棵树的树高一致的时候, 合并时会改变树高。
def union(self, x, y): rootX = self.find(x) rootY = self.find(y)
if rootX == rootY: return
# 按秩合并 if self.rank[rootX] < self.rank[rootY]: self.parent[rootX] = rootY else: self.parent[rootY] = rootX if self.rank[rootX] == self.rank[rootY]: self.rank[rootX] += 1TIPs
- 如果获得集合的个数?
- 方法一是初始化集合数为
n, 当每次union的时候减一; - 方法二是数根节点的数目
def get_count(self, first, last):count = 0while first != last:if self.parent[first] == first:count += 1first += 1return count - 方法一是初始化集合数为
参考
支持与分享
如果这篇文章对你有帮助，欢迎分享给更多人或赞助支持！