Disjoint Set

2025年10月22日

Disjoint Set

英語表記: Disjoint Set (または Disjoint Set Union, DSU)

概要

Disjoint Set（非交差集合）は、複数の要素を互いに共通の要素を持たない（非交差な）グループ（集合）に分割し、それらの集合を効率的に管理するための特殊データ構造です。この構造の主な役割は、任意の要素がどの集合に属しているかを追跡し、必要に応じて二つの集合を一つに統合することです。特に、要素間の接続関係や連結性を動的に判定・更新する必要があるアルゴリズムにおいて、非常に強力なツールとして機能します。データ構造の分類においては、「データ構造（リスト, スタック, キュー, ツリー）」という大枠の中の「集合管理構造」というニッチな領域を担っている、大変興味深い存在だと言えるでしょう。

詳細解説

目的と階層構造における位置づけ

Disjoint Setが目指すのは、複数の要素が時間経過とともにどのようにグループ化されていくかを、極めて高速に処理することです。もし、単純なリストや配列で集合管理を行おうとすると、集合の統合や所属の確認に時間がかかりすぎてしまいます。そこで、Disjoint Setは、この「集合管理」という特定の目的に特化した設計を採用しています。

この構造が「特殊データ構造」に分類されるのは、汎用的なリストやキューとは異なり、「Union（結合）」と「Find（検索）」という、たった二つの操作に特化しているからです。この特化こそが、驚異的な処理速度を実現する鍵となっています。

主要コンポーネントとUnion-Findアルゴリズム

Disjoint Setは、通常、各集合を表現するために木構造（ツリー）を利用します。ただし、一般的な二分探索木のような厳密なルールはなく、各集合は一つの代表元（ルートノード）によって識別されます。

このデータ構造を操作するアルゴリズム全体を、一般にUnion-Findアルゴリズムと呼びます。

1. Find操作（検索）

Find操作は、特定の要素がどの集合に属しているかを調べます。具体的には、その要素から親ノードをたどり、最終的に集合の代表元（ルート）に到達するまで繰り返します。このルートノードが、その要素が属する集合の「名前」の役割を果たします。

2. Union操作（結合）

Union操作は、二つの集合を一つに統合します。これは、一方の集合の代表元を、もう一方の集合の代表元の直接の子として接続することで実現されます。例えば、要素Aの集合の代表元を、要素Bの集合の代表元の子にする、といった具合です。どちらの代表元をどちらの子にするかによって、木の構造が変わります。

効率化のための工夫（必須知識）

Union-Findの魅力は、その高速性にあります。もし素朴にUnionとFindを行うだけでは、木がどんどん深くなり、Find操作の効率が悪化してしまいます。そこで、以下の二つのテクニックを併用することで、処理速度を極限まで高めています。これは、応用情報技術者試験レベルを目指すならぜひ押さえておきたいポイントです。

1. 経路圧縮 (Path Compression)

Find操作を実行する際、ルートノードにたどり着くまでの経路にあるすべてのノードを、直接ルートノードに接続し直す手法です。これにより、次に同じノードを検索する際には、たった一度のステップでルートに到達できるようになります。これは「手間を一度かけることで、未来永劫の効率を高める」という、非常に賢い工夫だと感心しますね。

2. ランクまたはサイズによる結合 (Union by Rank/Size)

Union操作を行う際、木の深さ（ランク）や要素数（サイズ）を考慮します。常に「浅い木」や「小さい集合」を「深い木」や「大きい集合」に接続するようにルール化します。これにより、木の深さが不必要に増大するのを防ぎ、結果としてFind操作にかかる時間を短縮できるのです。

これらの最適化を組み合わせることで、Union-Findアルゴリズムは実質的に定数時間に近い、非常に高い効率（アッカーマン関数の逆関数 $\alpha(n)$ に比例する計算量）を実現しています。これは、大規模なデータセットを扱う上で、驚異的な性能だと言えるでしょう。

具体例・活用シーン

Disjoint Setは、抽象的なデータ構造ですが、現実世界やアルゴリズムの世界では非常に重要な役割を果たしています。

活用シーンの具体例

ネットワークの連結性判定: ネットワーク上のノード（PCやルータ）が接続されているかどうかを判断したり、新たな接続が追加されたときに全体のネットワークが一つに繋がったかを判定したりする際に使われます。
最小全域木 (Minimum Spanning Tree, MST): グラフ理論の有名な問題であるMSTを求める「クラスカル法」は、まさにDisjoint Setを使ってエッジ（辺）の追加による連結性の変化を追跡しています。
迷路生成: ランダムに壁を取り除いていく迷路生成アルゴリズムにおいて、すべてのセルが最終的に一つの巨大な集合（つまり、迷路のすべての場所に行ける状態）になるまで、セルの結合状態を管理するために使われます。

初心者向けのアナロジー：村と村長の物語

Disjoint Setの動作を理解するために、「村と村長の物語」を考えてみましょう。

昔々、多くの小さな村（要素）がありました。それぞれの村は、独立した村長（代表元）によって治められていました。

集合（村）: 村人たちは、自分がどの村に属しているかを意識しています。これが集合です。
Find操作（所属確認）: ある村人が「自分の村長は誰だろう？」と尋ねる行為がFind操作です。彼は自分の親（直前の指導者）に尋ね、その親がまたその親に尋ねる、というように、情報が村長（ルート）にたどり着くまで伝言ゲームを続けます。
Union操作（村の合併）: 政治的な理由で二つの村が合併することになりました。Union操作では、一方の村の村長が、もう一方の村の村長の部下になる形で統合されます。これで二つの村は一つの大きな集合となります。

経路圧縮の導入: さて、Find操作で自分の村長が誰かを調べたとき、村人たちは賢いことを考えました。一度村長にたどり着いたら、次に誰かに尋ねられたときのために、自分の情報を直接、新しい村長に書き換えてしまうのです。これが経路圧縮です。最初は遠回りして村長にたどり着いたとしても、一度経路圧縮を行えば、次回からは「私の村長は〇〇です！」と即座に答えられるようになります。これによって、村人全体（データ構造全体）の効率が飛躍的に向上するわけです。

このように、Disjoint Setは、要素間の関係性や所属を動的に、かつ効率的に管理するために、非常に洗練された工夫が凝らされているデータ構造なのです。