Python实现并查集：基础结构与路径压缩优化详解

并查集（Disjoint Set）是一种基于树形结构的数据结构，主要用于处理不相交集合的合并操作以及查询元素所属集合的问题。在实际应用中，并查集通常以森林的形式存在，即由多棵独立的树组成。

并查集主要包含三种核心操作：一是获取节点所在的根节点；二是判断两个节点是否属于同一个集合（即是否连通）；三是将两个不属于同一集合的节点所在的集合进行合并。

我们可以定义一个名为UnionFind的类来封装并查集的逻辑。在构造函数中，初始化一个parent数组，其中parent[i]表示索引为i的节点的直接父节点。初始状态下，所有节点互不相连，因此将parent[i]初始化为i，即让每个节点直接指向自己作为根节点，从而实现各节点独立的状态。

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

由于parent数组仅记录了每个节点的直接父节点，要判断两个节点是否连通，必须比较它们各自根节点是否相同。因此，我们需要封装一个专门用于查询节点根节点的方法。

  def get_root(self, i):
    while i != self.parent[i]:
      i = self.parent[i]

    return i

基于上述根节点查询方法，我们可以通过比较两个节点的根节点是否一致，来判断这两个节点是否连通。

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

当需要合并两个节点所在的集合时，策略是将其中一个节点的根节点的parent指针指向另一个节点的根节点。需要注意的是，这一操作并非仅仅连接两个具体节点，而是将它们各自所属的整个集合进行合并。

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

接下来，我们将对基础实现进行两处关键的性能优化。

在调用get_root方法时，需要通过不断向上查找直接父节点来定位根节点。如果树的层级过深，查询性能将显著下降。因此，在union操作中，我们应尽可能控制合并后树的高度，以维持较高的查询效率。

在构造函数中，除了parent数组外，还需新建一个rank数组。rank[i]用于记录节点i所在集合的树的高度（或秩）。

在合并两棵树时，首先分别获取节点i和节点j的根节点i_root和j_root。随后，通过比较rank[i_root]和rank[j_root]的值来决定合并方向：将高度较小的树挂载到高度较大的树下。若两棵树高度相等，则任意选择一方作为父节点，并将其rank值加1，以反映新树高度的增加。

  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方法需要逐层向上查找父节点，耗时较多。鉴于根节点的父节点即为其自身，我们可以引入路径压缩策略：在递归查找根节点的过程中，将当前节点的父节点直接设置为根节点。这样，下次查询时即可直接访问根节点，大幅减少后续查询的时间开销。

  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]

以上即为使用Python实现并查集的完整过程，包括基础结构及路径压缩优化。希望这些内容能对读者的学习有所帮助，也欢迎大家继续支持本站获取更多技术资源。