アルゴリズム - 11. Union-Find (素集合データ構造)

Union-Findを使う場面

Union-Findは動的グラフにおける連結性を効率的に追跡したり、素集合を管理する必要がある場合に使用します。最もよく使われるのは連結成分の探索ですが、以下のような問題にも応用できます：

グラフの連結成分（古典的な使用例）
無向グラフのサイクル検出
最小全域木を求めるクラスカル法
ネットワーク連結性問題（サーバー、友達、アカウント）
パーコレーション問題（物理シミュレーション、迷路生成）
要素が同じグループに属するかを効率的に確認し、グループを結合する必要がある任意の問題

例題

ソーシャルネットワーク：[[1,2], [2,3], [4,5], [6,7], [5,6]]のような友達関係のリストが与えられたとき、以下を効率的に回答します：

人物1と人物3は友達ですか（直接または相互の繋がりを通じて）？
独立した友達グループはいくつ存在しますか？
新しい友達関係が生まれたときに、2つの友達グループを結合できますか？

すべての友達関係を処理した後：

グループ1：{1, 2, 3} - 友達関係を通じてすべて繋がっている
グループ2：{4, 5, 6, 7} - 友達関係を通じてすべて繋がっている
合計：2つの独立した友達グループ

答え：人物1と3は繋がっています（同じグループ）、合計2つのグループがあり、はい、効率的にグループを結合できます。

Union-Findが実際に行うこと

Union-Findは要素のグループを管理するデータ構造です。正確に2つの操作を提供します：

FIND：要素がどのグループに属するかを判定（グループの代表/ルートを返す）
UNION：2つのグループを1つのグループに結合

ソーシャルメディアの友達サークルを管理するようなものと考えてください：

FIND：「アリスはどの友達サークルに属していますか？」
UNION：「ボブとキャロルが友達になったので、彼らの友達サークルを結合します」

操作の仕組み

FIND操作 - 「この要素はどのグループにいますか？」

find(5)を呼び出すと：

要素5から開始
ルートまで親ポインタを辿る（ルートはグループ識別子）
常にルートを返す - このルートが全グループの一意のIDとして機能
最適化：走査中にパスを圧縮し、将来の検索を高速化

UNION操作 - 「これら2つのグループを接続」

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）を返す

// 一般的な使用法：2つの要素が接続されているかを確認
uf.isConnected(1, 3); // 内部でfind(1)とfind(3)を呼び出す

Union-Findの素晴らしい点は、2つのルートを接続するだけで瞬時に全グループが結合されることです - 各グループのすべての要素を更新する必要はありません！

最も重要な洞察

すべての要素は正確に1つの親を指し、集合を表す木を形成します - そして木を平坦にし（パス圧縮）、木の高さで結合する（ランクによる結合）ことで、代表の探索と集合の結合の両方でほぼ定数時間の操作を実現します。

メンタルノート：アルゴリズムの天才性は、集合をすべての要素が最終的に1つの「ルート」代表を指す木として扱うことにあります。各操作で必要なのは：(1) 親ポインタを辿ってルートを見つける（将来の検索を高速化するために圧縮）、または (2) 2つのルートを接続して全集合を結合すること。このシンプルな親ポインタメカニズムが自動的に素集合を効率的に維持します。

判断フレームワーク

Union-Findには2つの主要な判断が含まれます：

Find中（パス圧縮）：

親ポインタをルートまで辿る
ノードを直接ルート（または祖父母）に向けることでパスを圧縮

Union中（ランクによる結合）：

両方の要素のルートを見つける
異なるルートの場合：小さい木を大きい木の下に接続
同じルートの場合：すでに接続されているので、何もしない

「木の高さによる結合」が重要な理由

ランクによる結合は常に低い木を高い木の下に接続することを意味し、木をできるだけ平坦に保ちます。これが重要な理由を説明します：

ランクによる結合なし（悪い）：

常に最初の木に接続すると連鎖を作成：
1 → 2 → 3 → 4 → 5 → 6 → 7 → 8
高さ：8（要素8を見つけるのに8ステップかかる！）

ランクによる結合あり（良い）：

低い木を高い木に接続するとバランスの取れた木を作成：
        1
      / | \
     2  3  6
    / \   / \
   4   5 7   8
高さ：3（どの要素も最大3ステップで見つかる！）

「ランク」は木の高さです。2つの木を結合するとき：

一方の木が高い場合：低い木を高い木のルートの下に接続
両方同じ高さの場合：どちらでも接続できるが、結果の木のランクを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：ルートを接続して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増加（2つの同じランクの木が結合）
      this.rank.set(root2, rank2 + 1);
    }

    return true; // 2つのグループを正常に結合
  }

  // ヘルパー：2つの要素が同じグループにあるかを確認
  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. ランクは1つのことにのみ使用されます：union中の親の選択

// ランクが重要な唯一の場所：
if (rank1 > rank2) {
  parent[root2] = root1; // 高いランクが親になる
}

どのルートが親になるかを決定したら、各木の内部構造は将来のunionに影響しません - ルートのランクだけが重要です。

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ノード ✓
2つのランク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を得るには、2つのランクr-1の木を結合する必要がある
各ランク増加で最小ノード数が倍になる
したがって：n個のノード → 最大ランク = log₂(n)
パス圧縮なしでも、find()はO(n)ではなくO(log n)！

これがランクによる結合が機能する理由です：線形連鎖を防ぎ、総パス長を最小化します。ランクが高さについて「間違っている」場合でも、O(n)操作への最悪のケースの劣化を防ぐことについては「正しい」のです！

具体例：ランクを更新することが高価で不必要な理由

パス圧縮の後でランクを更新した場合を想像してみてください：

find(deepElement) {
  // ... パス圧縮を行う ...

  // 今、私たちは次のことをする必要があります：
  // 1. 実際の高さを見つけるために全木を走査
  // 2. ルートのランクを更新
  // 3. これはO(α(n))をO(n)に変える - ひどい！
}

ランクを更新するには、各圧縮後に全木構造を調べる必要があります - これは私たちが一生懸命に達成したほぼ定数時間の計算量を破壊します！

この「壊れた」システムが実際に機能する理由

素晴らしい洞察は、正確な高さは全く必要ないということです。理由は次のとおりです：

ランクは木のサイズの代理になる - 数学的に証明：ランクrは≥2^r個のノードを保証
高いランク = 指数的に多くのノード - ランク10はランク2より256倍多くのノードを持つ（最小）
小さいものを大きいもの（ノード数で）に接続すると木がバランスを保つ - そしてランクがこれを達成する！
パス圧縮がすべてを修正 - unionが完璧でなくても、圧縮がすべてのパスを平坦化

美しいパラドックス

ランクが高さの測定として完全に意味がなくなることを受け入れることで：

高価な高さ再計算を避ける（O(α(n))計算量を維持）
ランクはまだunionの決定に有用なヒューリスティックを提供（サイズとの相関を通じて）
パス圧縮が悪い決定をカバー
ランクが「間違っている」にもかかわらず、2つの最適化が協力

結論：ランクが実際の高さから完全に切り離されているのはバグではありません - 機能です！アルゴリズムは実際には正確な高さを必要としないので機能します。ランクは、木のサイズと偶然相関する過去の結合の「化石記録」として機能し、パス圧縮と組み合わせれば十分です。