algorithm - 互いに素な集合に対してどのような操作を実行できますか？

Question

素集合データ構造を調べたところ、「ユニオン検索データ構造」とも呼ばれ、ユニオンと検索がこのデータ構造の2つの主要な操作であることがわかりました。互いに素な集合に対して結合を実行できます。同様に、検索操作を実行できます。unionとfindを除いて、互いに素な集合に対して実行できる他の操作を知りたいです。

Answer 1

素集合構造は「ユニオンファインド構造」とも呼ばれます。したがってunion、とにかく操作をサポートする必要がありますfind。MakeSet他の操作は、この構造のすべてではありません。それらがサポートされているかどうかは、実装と目的によって異なります。プロジェクトの追加操作のニーズに合わせて、特定の実装を選択する必要がある場合があります。

それ以外は、他の基本的なセット関連の操作をサポートしていただければ幸いです。それらを列挙しましょう：

• 2つのセットの共通部分。セットは互いに素であるため、これら2つのセットが一致しない限り、常に空になります。
• 2つのセットの和集合-箱から出してサポートされます。
• セットから要素を取得します-サポートされています。ほとんどの場合、の結果ですfind。
• セットから要素を削除します-実装によって異なります。セットがフォレストとして実装される場合、それはトリッキーであり、より遅い追加操作を必要とします。セットがリンクリストとして実装される場合、それは簡単です。
• セットを列挙します。つまり、指定されたセットの各要素を繰り返します。これも実装に依存します。リンクリストの場合は単純ですが、フォレストのような実装の場合は、サポートする追加の構造が必要です。

Answer 2

バニラユニオン検索データ構造では、実際のセットを列挙できないため、セット操作の多くは使用できません。これは、バニラバージョンでは、一方向にしかポインターがないためです---下の図では、すべての対角線が上向きの矢印に対応し、ルート（一番上の線）がセットのルートオブジェクトです。

     o [set1]         o [Set2]
    / \                \
   o   o                o
  /
 o

したがって、たとえばセット1のすべてのオブジェクトを見つける方法はありません。たとえば、ルートノードからそれらへのパスをトレースすることはできません。下向きのポインタを使用することもできますが、オブジェクトはデータ構造内に任意の数の親を持つことができるため、データ構造が大幅に複雑になります。

したがって、実際には次の操作がほとんどです。

• 回答：私のオブジェクトAとBは同じセットに属しているかどうか？
• セットS1とS2をマージして、セット内のすべてのオブジェクトが同じセットに属していると見なされるようにします。

これを詳しく説明すると、和集合データ構造は、サポートする操作の時間計算量が非常に低くなります。セットのマージと同じセットのクエリへの回答はどちらも、償却された定数時間（O（1））を要します。この非常に時間の複雑さのために、すべての設定操作をサポートすることはできません。たとえば、標準の集合表現は[バイナリ]検索ツリーによるものであり、ほとんどの操作には少なくともO（log n）の複雑さがあります。

Answer 3

union-findの素集合構造のポイントは、あなたの質問や他の回答者が示唆しているように、基本的な集合演算を実行することではありません。代わりに、特定のアルゴリズムが必要とする構造の非常に効率的な実装であることが重要です。特に、連結成分と最小全域木を見つけることは、union-findの素集合の上に最も効率的な実装を構築します。