EnlightenCode

并查集(Union-Find)入门指南 ​

什么是并查集? ​

并查集是一种简洁优雅的数据结构,主要用于处理元素分组的问题。它的特点是:

  • 可以高效地管理一系列不相交的集合
  • 支持两个核心操作:合并(Union)和查找(Find)
  • 在前端开发中常用于:社交网络、网络连接、组件状态管理等场景

核心API设计 ​

  1. 构造函数: 初始化并查集
  2. find(): 查找元素所属的组
  3. union(): 合并两个组
  4. isSame(): 判断两个元素是否在同一组
  5. getCount(): 获取当前分组数量

代码实现 ​

js
class UnionFind {
  constructor(n) {
    this.parent = [] // 存储节点的父节点
    this.size = []   // 存储每个根节点的子树大小
    this.count = 0   // 当前分组数量
    this.init(n)
  }

  // 初始化
  init(n) {
    this.parent = Array.from({length: n}, (_, i) => i) // 初始时每个节点指向自己
    this.size = new Array(n).fill(1)
    this.count = n
  }

  // 查找节点所属的组(根节点)
  find(node) {
    while (node !== this.parent[node]) {
      // 路径压缩优化: 将查找路径上的所有节点直接指向根节点
      this.parent[node] = this.parent[this.parent[node]]
      node = this.parent[node]
    }
    return node
  }

  // 合并两个组
  union(left, right) {
    const leftRoot = this.find(left)
    const rightRoot = this.find(right)
    
    if (leftRoot !== rightRoot) {
      // 按秩合并优化: 将小树合并到大树下
      if (this.size[leftRoot] < this.size[rightRoot]) {
        this.parent[leftRoot] = rightRoot
        this.size[rightRoot] += this.size[leftRoot]
      } else {
        this.parent[rightRoot] = leftRoot
        this.size[leftRoot] += this.size[rightRoot]
      }
      this.count--
      return true
    }
    return false
  }

  // 其他辅助方法...
}

性能优化 ​

  1. 路径压缩: 在find操作时将路径上的节点直接指向根节点,降低树的高度
  2. 按秩合并: 合并时将小树合并到大树下,保持树的平衡

实际应用场景 ​

  1. 好友关系网络
  2. 网站账号合并
  3. React组件状态管理
  4. 网络连接判断

复杂度分析 ​

  • 时间复杂度: 接近O(1) [使用路径压缩和按秩合并后]
  • 空间复杂度: O(n)

练习题推荐 ​

  1. LeetCode 547: 省份数量
  2. LeetCode 200: 岛屿数量
  3. LeetCode 684: 冗余连接