14. Disjoint Sets

Disjoint Sets

如果两个集合没有任何共同元素，则称为 Disjoint Sets（不相交集合）。

算法改进过程

目标：实现两个操作

• connect：连接两个元素
• isConnected：判断是否连通

1. 天真方法

逐一检查所有连接关系来判断连通性。
问题：

• 时间复杂度过高
• 实际应用中不可行

2. Connected Components & Quick Find

思路：
将所有互相连通的元素归为同一个集合。

方法一：ListOfSetsDS

创建一个列表包含所有的集合，集合内存储所有连通的分量
问题：

• 结构复杂
• 操作代价高
• 时间复杂度不可接受

方法二：QuickFindDS

使用一个 id 数组表示集合归属：

• 同一集合的元素拥有相同的 id

特点：

• isConnected 很快
• connect 很慢（需要遍历并修改大量 id）

3. Quick Union

问题来源：
QuickFind 在 connect 时效率过低。

改进思路：
使用树结构表示集合，每个节点记录其父节点（parent）。

示例：

• 2 → 1 → 0 → -1
• 根节点（root）为 0

操作：

• connect(5, 2)：
  1. 找到 5 和 2 的 root
  2. 将其中一个 root 连接到另一个

特点：

• connect 更快
• 但树可能退化成链，导致查找变慢

4. Weighted Quick Union

问题来源：
QuickUnion 可能形成“高瘦树”，查找效率下降。

改进策略：

• 记录每棵树的大小
• 始终将小树连接到大树

实现要点：

1. 维护每个树的节点数量
2. 合并时按大小决定方向

示例：
调用 connect(3, 8) 时，将较小的树连接到较大的树：

效果：

• 树高度显著降低
• 时间复杂度明显优化

5. Path Compression

问题来源：
即使是上面的办法，查找 root 仍可能较慢。

示例结构：

调用 isConnected(15, 10) 时，需要多次向上查找。

优化思路：
在查找 root 的过程中，将路径上的所有节点直接连接到 root。

优化后结构：

该方法称为：
WeightedQuickUnionDSWithPathCompression

效果：

• 极大降低树高度
• 后续操作几乎为常数时间

总结

• 使用“连通分量”来表示集合（而不是跟踪每一条具体连接关系）
• ListOfSetsDS：用“集合的列表”存储连通分量（速度慢、结构复杂）
• QuickFindDS：用集合编号（set id）表示连通分量
• QuickUnionDS：用父节点编号（parent id）表示连通分量
• WeightedQuickUnionDS：额外记录每个集合的大小，并据此决定新的树根
• WeightedQuickUnionWithPathCompressionDS：在调用 connect 和 isConnected 时，将路径上的所有节点直接连接到根节点