算法 - 11. 并查集（不相交集合）

何时使用并查集

当你需要高效追踪动态图中的连通性或管理不相交集合时，使用并查集。虽然最常用于查找连通分量，但它也可以适用于：

图中的连通分量（经典用例）
无向图中的环检测
查找最小生成树的克鲁斯卡尔最小生成树算法
网络连通性问题（服务器、朋友、账户）
渗透问题（物理模拟、迷宫生成）
任何需要高效合并组并检查元素是否属于同一组的问题

示例问题

社交网络：给定一个友谊列表，如[[1,2], [2,3], [4,5], [6,7], [5,6]]，高效回答：

第1个人和第3个人是朋友吗（直接或通过共同联系）？
存在多少个独立的朋友组？
当形成新的友谊时，我们能合并两个朋友组吗？

处理所有友谊后：

组1：{1, 2, 3} - 所有人通过友谊连接
组2：{4, 5, 6, 7} - 所有人通过友谊连接
总计：2个独立的朋友组

答案：第1个人和第3个人是连通的（同一组），我们有2个总组，是的，我们可以高效地合并组。

并查集实际做什么

并查集是一个管理元素组的数据结构。它恰好提供两个操作：

FIND：确定一个元素属于哪个组（返回组的代表/根）
UNION：将两个组合并为一个组

将其想象成管理社交媒体上的朋友圈：

FIND："Alice属于哪个朋友圈？"
UNION："Bob和Carol刚成为朋友，合并他们的朋友圈"

操作的工作原理

FIND操作 - "这个元素在哪个组中？"

当你调用find(5)时，它：

从元素5开始
沿着父指针向上到根（根是组标识符）
总是返回根 - 这个根作为整个组的唯一ID
优化：在遍历时压缩路径，使未来的查找更快

UNION操作 - "连接这两个组"

当你调用union(3, 7)时，它：

找到元素3的组的根
找到元素7的组的根
如果根相同：它们已经连接，什么也不做
如果根不同：让一个根指向另一个，立即合并整个组

这些操作何时发生

这些操作只在你明确调用它们时发生：

const uf = new UnionFind(10);

// UNION: 明确连接元素
uf.union(1, 2); // 连接包含1和2的组
uf.union(2, 3); // 连接包含2和3的组

// FIND: 检查元素属于哪个组
let groupID = uf.find(3); // 总是返回根（组的唯一ID）

// 常见用法：检查两个元素是否连通
uf.isConnected(1, 3); // 内部调用find(1)和find(3)

并查集的美妙之处在于，仅连接两个根就能立即合并整个组 - 你不需要更新任一组中的每个元素！

最重要的洞察

每个元素恰好指向一个父节点，形成代表集合的树 - 通过使树扁平（路径压缩）和按树高度合并（按秩合并），我们在查找代表和合并集合方面都实现了接近常数时间的操作。

思维要点：该算法的天才之处在于将集合视为所有元素最终指向一个"根"代表的树。在每次操作中，我们只需要：(1) 沿着父指针找到根（通过压缩加快未来查找），或 (2) 连接两个根来合并整个集合。这个简单的父指针机制自动高效地维护不相交集合。

决策框架

并查集涉及两个关键决策：

Find期间（路径压缩）：

沿着父指针到根
通过让节点直接指向根（或祖父节点）来压缩路径

Union期间（按秩合并）：

找到两个元素的根
如果根不同：将较小的树附加到较大的树下
如果根相同：元素已连接，什么也不做

为什么"按树高度合并"很重要

按秩合并意味着总是将较短的树附加到较高的树下以保持树尽可能扁平。这很关键的原因如下：

没有按秩合并（糟糕）：

总是附加到第一棵树会创建链：
1 → 2 → 3 → 4 → 5 → 6 → 7 → 8
高度：8（找到元素8需要8步！）

使用按秩合并（良好）：

将较短的附加到较高的会创建平衡树：
        1
      / | \
     2  3  6
    / \   / \
   4   5 7   8
高度：3（找到任何元素最多需要3步！）

"秩"是树的高度。当合并两棵树时：

如果一棵树较高：将较短的树附加到较高树的根下
如果两者高度相同：可以附加到任一方，但将结果树的秩增加1
结果：最大高度以对数而非线性增长

这种优化确保即使没有路径压缩，操作仍保持O(log n)，而有了路径压缩，我们实现了接近常数时间！

代码

class UnionFind {
  constructor(numberOfElements) {
    // 存储父指针：parent[element] = element的父节点
    // 最初，每个元素是它自己的父节点（意味着它是根）
    this.parent = new Map();

    // 存储树的秩：rank[element] = 树高度的上界
    // 用于在union操作期间保持树平衡
    // 注意：路径压缩后，这成为估计值，而不是实际高度！
    this.rank = new Map();

    // 初始化：创建numberOfElements个独立的组
    // 每个元素从自己的组开始（指向自己）
    for (let element = 1; element <= numberOfElements; element++) {
      this.parent.set(element, element); // 自循环意味着"我是根"
      this.rank.set(element, 0); // 单个元素的秩为0
    }
  }

  // FIND: 返回元素的根/组ID
  // 同时压缩路径以加快未来的操作
  find(element) {
    // 从元素开始，沿着父指针向上
    let current = this.parent.get(element);

    // 继续向上爬树直到找到根
    // （根由parent[root] === root标识）
    while (current !== this.parent.get(current)) {
      // 决策框架：路径压缩优化
      // 爬树时，让每个节点指向其祖父节点
      // 这会扁平化树结构
      const parentOfCurrent = this.parent.get(current);
      const grandparent = this.parent.get(parentOfCurrent);
      this.parent.set(current, grandparent);

      // 移动到下一层
      current = this.parent.get(current);
    }

    // 我们已经到达根 - 这是组ID
    return current;
  }

  // UNION: 合并包含element1和element2的组
  // 如果合并返回true，如果已在同一组返回false
  union(element1, element2) {
    // 步骤1：找到每个元素属于哪个组
    const root1 = this.find(element1);
    const root2 = this.find(element2);

    // 决策框架：检查是否已连接
    if (root1 === root2) {
      // 两个元素已经在同一组中
      return false;
    }

    // 步骤2：通过连接它们的根来合并两个组
    // 决策框架：按秩合并 - 保持树平衡
    const rank1 = this.rank.get(root1);
    const rank2 = this.rank.get(root2);

    if (rank1 > rank2) {
      // 树1具有更高的秩 - 使其成为父节点以保持平衡
      this.parent.set(root2, root1);
      // 秩不变（较小秩树附加到较大秩树）
    } else if (rank1 < rank2) {
      // 树2具有更高的秩 - 使其成为父节点以保持平衡
      this.parent.set(root1, root2);
      // 秩不变（较小秩树附加到较大秩树）
    } else {
      // 两棵树秩相同 - 选择任一作为父节点
      this.parent.set(root1, root2);
      // 秩增加1（两个相同秩的树合并）
      this.rank.set(root2, rank2 + 1);
    }

    return true; // 成功合并两个组
  }

  // 辅助：检查两个元素是否在同一组中
  isConnected(element1, element2) {
    // 如果元素具有相同的根，则它们是连通的
    return this.find(element1) === this.find(element2);
  }
}

// === 使用示例：社交网络问题 ===
// 我们有7个人（编号1-7）
const socialNetwork = new UnionFind(7);

// 要处理的友谊列表
const friendships = [
  [1, 2], // 第1个人和第2个人成为朋友
  [2, 3], // 第2个人和第3个人成为朋友（现在1,2,3都连通了！）
  [4, 5], // 第4个人和第5个人成为朋友
  [6, 7], // 第6个人和第7个人成为朋友
  [5, 6], // 第5个人和第6个人成为朋友（现在4,5,6,7都连通了！）
];

// 处理每个友谊（合并朋友组）
console.log("处理友谊：");
for (const [person1, person2] of friendships) {
  const wasNewConnection = socialNetwork.union(person1, person2);
  if (wasNewConnection) {
    console.log(`连接了第${person1}个人和第${person2}个人的组`);
  } else {
    console.log(`第${person1}个人和第${person2}个人已在同一组`);
  }
}

// 检查特定的人是否是朋友（直接或间接）
console.log("\n检查连接：");
console.log(`1和3是朋友吗？ ${socialNetwork.isConnected(1, 3)}`); // true
console.log(`1和4是朋友吗？ ${socialNetwork.isConnected(1, 4)}`); // false
console.log(`4和7是朋友吗？ ${socialNetwork.isConnected(4, 7)}`); // true

// 计算存在多少个独立的朋友组
const uniqueGroups = new Set();
for (let person = 1; person <= 7; person++) {
  const groupID = socialNetwork.find(person);
  uniqueGroups.add(groupID);
}
console.log(`\n朋友组总数：${uniqueGroups.size}`); // 2个组

疑惑解答

常见疑惑："路径压缩极大地改变了树结构，但我们之后从不更新秩。这不会搞乱我们精心维护的秩吗？这不是一个错误吗？"

这看起来像是一个严重的不一致 - 我们使用秩来保持树平衡，但路径压缩在不更新秩的情况下扁平化树。让我们探讨为什么这个明显的"错误"实际上是一个出色的设计决策。

为什么这看起来是错的

考虑路径压缩会发生什么：

find(5)之前：                路径压缩后find(5)：
    1 (秩=3)                     1 (秩=3 - 未改变！)
    |                           /|\\
    2 (秩=2)                   2 3 4 5
    |
    3 (秩=1)
    |
    4 (秩=0)
    |
    5 (秩=0)

实际高度：5                   实际高度：2
存储的秩：3                   存储的秩：仍然是3！

树从高度5变为高度2，但秩保持为3。这看起来完全错误！

关键洞察：秩对高度变得无意义

这是关键的认识：路径压缩开始后，秩完全与实际树高度脱节。

秩可能完全错误 - 甚至不是估计值：

秩10的树可能实际高度为1（经过激进压缩后）
秩3的树可能实际高度为3（如果从未压缩）
秩对当前结构一无所知

为什么我们不需要更新秩

1. 秩只用于一件事：在union期间选择父节点

// 秩重要的唯一地方：
if (rank1 > rank2) {
  parent[root2] = root1; // 更高的秩成为父节点
}

一旦我们决定哪个根成为父节点，每棵树的内部结构不会影响未来的unions - 只有根的秩重要。

2. 路径压缩只影响非根节点

压缩前：              压缩后：
    1 (秩=2)             1 (秩=2)
    |                   /|\
    2                  2 3 4
    |
    3
    |
    4

节点1仍然是根！
节点1的秩对于union决策仍然有效！
节点2,3,4无论如何都没有有意义的秩（它们不是根）

3. 即使完全错误的秩仍然防止最坏情况

令人惊讶的是 - 即使秩完全错误，它们仍然有帮助：

树A（秩=10，大规模压缩后实际高度=1）：
    A
   /|\\...
  （50个节点都是直接子节点）

树B（秩=2，实际高度=2）：
    B
    |
    C
    |
    D

Union(A,B) → B附加在A下（秩10 > 秩2）

为什么这仍然有帮助：
- 树A有秩10是因为它在某个时候很高
- 它通过吸收许多树获得了那个秩
- 即使现在很扁平，它可能有更多节点
- 将较小的树附加到较大的（按节点数）仍然很好！

关键洞察：秩意外地与树大小（节点数）相关，即使它们对高度完全错误！

这可以数学证明吗？

实际上，可以！秩和最小节点数之间有数学关系：

定理：秩为r的树包含至少2^r个节点。

归纳法证明：

基本情况：秩0 = 单个节点 = 2^0 = 1个节点 ✓
当我们合并两个秩r的树时：我们得到秩r+1，至少有2^r + 2^r = 2^(r+1)个节点 ✓
路径压缩从不改变秩或删除节点
因此：秩r → 至少2^r个节点总是成立

示例：

秩10的树 → 至少有2^10 = 1,024个节点
秩2的树 → 至少有2^2 = 4个节点
所以将秩2的树附加到秩10的树下是有意义的！

为什么将较小秩附加到较大秩是最优的：

考虑最大可能的find()路径长度会发生什么：

选项A：将秩2的树附加到秩10的树下

秩10树中的节点：它们的路径不变
秩2树中的节点：它们的路径增加1
最受影响的：最多2^2 = 4个节点获得更长的路径
总"成本"：4个节点 × 1额外步骤 = 4单位

选项B：将秩10的树附加到秩2的树下

秩2树中的节点：它们的路径不变
秩10树中的节点：它们的路径增加1
最受影响的：至少2^10 = 1,024个节点获得更长的路径
总"成本"：1,024个节点 × 1额外步骤 = 1,024单位

数学结论：

选项A对≤4个节点产生负面影响
选项B对≥1,024个节点产生负面影响
选项A比选项B好256倍！

最重要的是，这防止了最坏情况场景：

没有按秩合并，我们可以创建一个高度为n的n个元素的链：

1 → 2 → 3 → 4 → ... → n（高度 = n，find() = O(n)）

使用按秩合并，最大高度是对数的：

最大高度 ≤ log₂(n)
具有n个节点的树 → 秩 ≤ log₂(n) → 高度 ≤ log₂(n)

为什么这个保证成立：

要获得秩r，你必须合并两个秩r-1的树
每次秩增加都会使最小节点数翻倍
因此：n个节点 → 最大秩 = log₂(n)
即使没有路径压缩，find()是O(log n)，而不是O(n)！

这就是按秩合并起作用的原因：它防止线性链并最小化总路径长度。即使秩对高度"错误"，它们对防止最坏情况退化到O(n)操作是"正确的"！

具体示例：为什么更新秩会很昂贵且不必要

想象一下如果我们在每次路径压缩后都更新秩：

find(deepElement) {
  // ... 执行路径压缩 ...

  // 现在我们需要：
  // 1. 遍历整棵树以找到实际高度
  // 2. 更新根的秩
  // 3. 这将O(α(n))变成O(n) - 糟糕！
}

更新秩需要在每次压缩后检查整个树结构 - 这将破坏我们努力实现的接近常数时间复杂度！

为什么这个"破损"的系统实际上有效

出色的洞察是我们根本不需要准确的高度。原因如下：

秩成为树大小的代理 - 数学证明：秩r保证≥2^r个节点
更高的秩 = 指数级更多的节点 - 秩10比秩2多256倍的节点（最少）
将较小的附加到较大的（按节点数）保持树平衡 - 秩实现了这一点！
路径压缩修复一切 - 即使unions不完美，压缩也会扁平化所有路径

美丽的悖论

通过接受秩作为高度测量完全无意义：

我们避免昂贵的高度重新计算（保持O(α(n))复杂度）
秩仍然为union决策提供有用的启发式（通过与大小的相关性）
路径压缩覆盖任何糟糕的决策
尽管秩"错误"，两种优化仍然协同工作

底线：秩完全与实际高度脱节不是错误 - 这是一个特性！该算法之所以有效，是因为它实际上不需要准确的高度。秩作为过去合并的"化石记录"，恰好与树大小相关，当与路径压缩结合时，这就足够了。