并查集算法中的按秩合并和路径压缩

引言

将一个集合分成不相交的子集是Union-Find算法（有时也称为不相交集数据结构）解决的问题。它的两个主要操作是Union（合并两个子集）和Find（确定特定元素属于哪个子集）。最初，每个元素都被视为一个独立的子集。

按秩合并

Union-Find数据结构采用按秩合并（Union by Rank）启发式方法将较小的树合并到较大的树中，以优化Union操作。每个子集或树都被赋予一个秩（或深度），它确保在Union操作期间较小的树合并到较大的树中，以避免形成所有树。

算法

步骤1：初始化

创建一个不相交的数据结构，这意味着每个元素最初都在一个单独的集合中。每个元素的集合的秩应设置为0。

步骤2：Union操作

当对两个元素执行Union操作时，找到每个元素的集合的代表（根元素）。

检查两个根元素的秩

• 如果秩不同，将一个集合的代表作为另一个集合的代表的父节点来合并这些集合。将秩较低的集合的成员分配为父节点。
• 如果秩相等，随机选择一个组的代表作为另一个集合的代表的父节点。提高父代表的秩。

步骤3：使用路径压缩的Find操作

• 递归地沿着父指针直到找到根元素，以确定元素的代表。
• 路径压缩可以通过将遍历路径上的每个访问过的节点直接指向根元素来实现。它优化了后续的Find操作并使树结构扁平化。

伪代码

示例

考虑一组元素：{0, 1, 2, 3, 4, 5}

1. 初始化

每个元素最初都在其子集中，秩为0。

2. Union操作

我们将执行多个Union操作

Union(0, 1)：两个子群的秩都是0。让我们随机选择0作为1的父节点。

• Union (2, 3)

两个子群的秩都是0。让我们随机选择2作为3的父节点。

• Union (4, 5)

两个子群的秩都是0。让我们随机选择4作为5的父节点。

• Union (1, 4)

包含根1和4的子集都具有秩0。假设1是4的父节点，让我们将其秩提高到1。

Find操作（带路径压缩）

让我们执行元素5的查找操作

• 初始路径为5 -> 5。
• 路径压缩后：5 -> 1

路径压缩

路径压缩是一种在不相交集数据结构（特别是Union-Find算法）中使用的优化方法。其主要目标是降低不相交集之间生成的树的高度，从而提高搜索操作的效率。

在不相交集数据结构中，每个元素都是一个不相交集的一部分，表示为一棵树，每个节点指向其父节点。当执行搜索操作以查找元素的根时，通常通过父指针从该元素到其根的路径。这种遍历可能导致路径更长，特别是在处理深层或不平衡的树时。

算法

1. 初始化

从一组不相交的集合开始，其中每个元素都是它自己的集合，并且它的父节点指向它自己。

2. Find操作

• 当使用搜索操作获取元素x的根时
• 如果x的父节点不是它自己（即parent[x]!= x），则x不是该集合的根。
• 递归地对x的父节点执行查找操作，直到到达根。
• 在到达根的途中，将每个遇到的节点的父引用更改为根。这个过程被称为路径压缩。

3. Union操作

当对两个项(x, y)执行Union操作时

• 使用查找操作来定位包含x和y的集合的根。
• 如果根不同，将其中一个作为另一个的父节点来合并这些集合。

伪代码

示例

考虑一个Union-Find数据结构，其元素{1, 2, 3, 4, 5}最初被分离成集合。

• 最初

• 执行Union操作union(1, 2)和union(2, 3)后，

• 对元素3应用查找操作后

路径压缩发生在搜索过程中。

从元素3到其根(1)的路径被压缩，导致元素3和2的父指针直接指向根。

• 执行Union操作后：union(4, 5)

• 对元素5应用查找操作后

路径压缩被实现，并且元素5的父指针被更新为直接指向其根(4)。

实施

输出

说明

• Subset结构表示一个子集，并有两个字段：parent，存储父元素；rank，存储子集的秩。
• makeSet函数创建子集，其中每个元素都是其父节点，并且秩为零。
• find函数识别包含元素的子集的根。路径压缩通过沿途更新父指针来扁平化树结构。
• unionSets函数对两个元素x和y执行Union操作。它采用按秩合并以确保操作效率。
• 在主函数中，我们初始化子集，执行Union操作，并验证Find操作的有效性。

结论

按秩合并和路径压缩提高了Union-Find方法的效率。通过平衡树和扁平化路径，这些策略减少了典型实现中的低效率，使Union-Find成为计算机科学和其他广泛应用领域的有价值工具。理解和执行这些优化对于在Union-Find过程中获得最佳性能至关重要。