并查集

概念

并查集是一种特殊的树结构，用于处理一些不交集的合并及查询问题。该结构中每个节点都有一个父节点，如果只有当前一个节点，那么该节点的父节点指向自己。

这个结构中有两个重要的操作，分别是：

  • Find：确定元素属于哪一个子集。它可以被用来确定两个元素是否属于同一子集。
  • Union：将两个子集合并成同一个集合。

并查集 - 图1

实现

  1. class DisjointSet {
  2.   // 初始化样本
  3.   constructor(count) {
  4.     // 初始化时，每个节点的父节点都是自己
  5.     this.parent = new Array(count)
  6.     // 用于记录树的深度，优化搜索复杂度
  7.     this.rank = new Array(count)
  8.     for (let i = 0; i < count; i++) {
  9.       this.parent[i] = i
  10.       this.rank[i] = 1
  11.     }
  12.   }
  13.   find(p) {
  14.     // 寻找当前节点的父节点是否为自己，不是的话表示还没找到
  15.     // 开始进行路径压缩优化
  16.     // 假设当前节点父节点为 A
  17.     // 将当前节点挂载到 A 节点的父节点上，达到压缩深度的目的
  18.     while (p != this.parent[p]) {
  19.       this.parent[p] = this.parent[this.parent[p]]
  20.       p = this.parent[p]
  21.     }
  22.     return p
  23.   }
  24.   isConnected(p, q) {
  25.     return this.find(p) === this.find(q)
  26.   }
  27.   // 合并
  28.   union(p, q) {
  29.     // 找到两个数字的父节点
  30.     let i = this.find(p)
  31.     let j = this.find(q)
  32.     if (i === j) return
  33.     // 判断两棵树的深度，深度小的加到深度大的树下面
  34.     // 如果两棵树深度相等，那就无所谓怎么加
  35.     if (this.rank[i] < this.rank[j]) {
  36.       this.parent[i] = j
  37.     } else if (this.rank[i] > this.rank[j]) {
  38.       this.parent[j] = i
  39.     } else {
  40.       this.parent[i] = j
  41.       this.rank[j] += 1
  42.     }
  43.   }
  44. }