筆記 前端需要了解的常見資料結構--并查集

概念

并查集是一種特殊的樹結構，用于處理一些不交集的合并及查詢問題。該結構中每個節點都有一個父節點，如果隻有目前一個節點，那麼該節點的父節點指向自己。

這個結構中有兩個重要的操作，分别是：

1. Find：确定元素屬于哪一個子集。它可以被用來确定兩個元素是否屬于同一子集。
2. Union：将兩個子集合并成同一個集合。

實作

class DisjointSet {
  // 初始化樣本
  constructor(count) {
    // 初始化時，每個節點的父節點都是自己
    this.parent = new Array(count)
    // 用于記錄樹的深度，優化搜尋複雜度
    this.rank = new Array(count)
    for (let i = 0; i < count; i++) {
      this.parent[i] = i
      this.rank[i] = 1
    }
  }
  find(p) {
    // 尋找目前節點的父節點是否為自己，不是的話表示還沒找到
    // 開始進行路徑壓縮優化
    // 假設目前節點父節點為 A
    // 将目前節點挂載到 A 節點的父節點上，達到壓縮深度的目的
    while (p != this.parent[p]) {
      this.parent[p] = this.parent[this.parent[p]]
      p = this.parent[p]
    }
    return p
  }
  isConnected(p, q) {
    return this.find(p) === this.find(q)
  }
  // 合并
  union(p, q) {
    // 找到兩個數字的父節點
    let i = this.find(p)
    let j = this.find(q)
    if (i === j) return
    // 判斷兩棵樹的深度，深度小的加到深度大的樹下面
    // 如果兩棵樹深度相等，那就無所謂怎麼加
    if (this.rank[i] < this.rank[j]) {
      this.parent[i] = j
    } else if (this.rank[i] > this.rank[j]) {
      this.parent[j] = i
    } else {
      this.parent[i] = j
      this.rank[j] += 1
    }
  }
}