Given a set of elements, it is often useful to break them up or partition them into a number of separate, nonoverlapping sets. A disjoint-set data structure is a data structure that keeps track of such a partitioning. A union-find algorithm is an algorithm that performs two useful operations on such a data structure: Find: Determine which set a particular element is in. Also useful for determining if two elements are in the same set. Union: Combine or merge two sets into a single set.

PropertyValue
dbpprop:abstract
  • Given a set of elements, it is often useful to break them up or partition them into a number of separate, nonoverlapping sets. A disjoint-set data structure is a data structure that keeps track of such a partitioning. A union-find algorithm is an algorithm that performs two useful operations on such a data structure: Find: Determine which set a particular element is in. Also useful for determining if two elements are in the same set. Union: Combine or merge two sets into a single set. Because it supports these two operations, a disjoint-set data structure is sometimes called a union-find data structure or merge-find set. The other important operation, MakeSet, which makes a set containing only a given element, is generally trivial. With these three operations, many practical partitioning problems can be solved (see the Applications section). In order to define these operations more precisely, some way of representing the sets is needed. One common approach is to select a fixed element of each set, called its representative, to represent the set as a whole. Then, Find(x) returns the representative of the set that x belongs to, and Union takes two set representatives as its arguments.
  • Eine Union-Find-Datenstruktur verwaltet die Partition einer Menge. Der abstrakte Datentyp wird durch die Menge der drei Operationen {Union, Find, Make-Set} gebildet. Union-Find-Strukturen dienen zur Verwaltung von Zerlegungen in disjunkten Mengen. Dabei bekommt jede Menge der Zerlegung ein kanonisches Element zugeordnet, welches als Name der Menge dient. Union vereinigt zwei solche Mengen, Find(x) bestimmt das kanonische Element derjenigen Menge, die x enthält und Make- Set erzeugt eine Einermenge {x} mit dem kanonischen Element x.
  • Étant donné un ensemble d'éléments, il est souvent utile de le partitionner en un certain nombre de classes disjointes, c'est-à-dire de représenter une relation d'équivalence. Une structure de données pour le problème des classes disjointes maintient une telle partition et comme elle a essentiellement deux opérations trouver et unir, on l'appelle union-find, suivant en cela la terminologie anglaise: Find (trouver): détermine la classe d'équivalence d'un élément; elle sert aussi à déterminer si deux éléments appartiennent à la même classe d'équivalence. Union (unir): réunit deux classes d'équivalence en une seule. Une autre opération importante, MakeSet, construit une classe d'équivalence contenant un seul élément, autrement dit un singleton. Afin de définir ces opérations plus précisément, il faut choisir un moyen de représenter les classes. L'approche traditionnelle consiste à sélectionner un élément particulier de chaque classe, appelé le représentant, pour identfier la classe entière. Lors d'un appel, Find(x) retourne le représentant de la classe de x.
  • L' MFSet (Merge-Find Set) è una struttura dati derivante dal concetto di Insieme delle parti, per cui dato un insieme finito di elementi a volte risulta utile partizionarli in insiemi disgiunti. L'algoritmo di Merg-Find è quindi utile per le due operazioni possibili su questa struttura dati: Ricerca: determina in quale insieme si trova un particolare elemento, o se due elementi appartengono allo stesso insieme Unione: combina o fonde due insiemi in un unico insieme L'altra operazione su MFSet è CreaMFSet tramite la quale è possibile dato un insieme crearne l'insieme delle parti di ciascun elemento. Con l'utilizzo di questi tre operatori è possibile risolvere molti problemi pratici.
  • 素集合データ構造（英: disjoint-set data structure）は、データの集合を素集合（互いにオーバーラップしない集合）に分割して保持するデータ構造。このデータ構造に対する以下の2つの便利な操作をUnion-Findアルゴリズムと呼ぶ。 Find: 特定の要素がどの集合に属しているかを求める。2つの要素が同じ集合に属しているかの判定にも使われる。 Union: 2つの集合を1つに統合する。 これら2つの操作をサポートしているため、素集合データ構造は「Union-Findデータ構造」あるいは「Merge-Find集合」とも呼ばれる。これら以外の重要な操作として MakeSetがある。これは、与えられた1つの要素だけを格納した集合（シングルトン）を作成する。これら3つの操作により、様々な実用的分割問題を解くことができる（「応用」の節を参照）。 これらの操作をより正確に定義するには、集合の表現方法を決める必要がある。典型的な手法としては、それぞれの集合について、ある固定の要素を選択して「代表 (representative)」とし、その集合全体を表すものとする。すると Find(x) は x が属する集合の代表を返す。また、Union は2つの代表を引数とする。
  • Struktura zbiorów rozłącznych to struktura danych, która przechowuje dla ustalonego zbioru (uniwersum) jego podział na mniejsze, rozłączne zbiory. Struktura taka umożliwia dwie operacje: Find: Wyznacza, w którym zbiorze jest dany element, pozwalając na sprawdzenie, czy dwa elementy są w tym samym zbiorze. Union: Łączy dwa zbiory w jeden. Czasem podaje się jeszcze trzecią operację, MakeSet, która dołącza do uniwersum nowy element jako jednoelementowy zbiór. Operacje te potrzebują jakiejś metody identyfikacji i odróżniania od siebie zbiorów. Najczęściej używa się w tym celu jednego, wyróżnionego elementu zbioru (zwanego reprezentantem).
  • Система непересекающихся множеств позволяет администрировать множество элементов разбитое на непересекающиеся подмножества. При этом каждому подмножеству назначается его представитель — элемент этого подмножества. Абстрактная структура данных определяется множеством трех операций {Union, Find, MakeSet.
  • 并查集是一种树型的数据结构，用于处理一些不相交集合（Disjoint Sets）的合并及查询问题。常常在使用中以森林来表示。
dbpprop:hasPhotoCollection
dbpprop:reference
rdf:type
rdfs:comment
  • Given a set of elements, it is often useful to break them up or partition them into a number of separate, nonoverlapping sets. A disjoint-set data structure is a data structure that keeps track of such a partitioning. A union-find algorithm is an algorithm that performs two useful operations on such a data structure: Find: Determine which set a particular element is in. Also useful for determining if two elements are in the same set. Union: Combine or merge two sets into a single set.
  • Eine Union-Find-Datenstruktur verwaltet die Partition einer Menge. Der abstrakte Datentyp wird durch die Menge der drei Operationen {Union, Find, Make-Set} gebildet. Union-Find-Strukturen dienen zur Verwaltung von Zerlegungen in disjunkten Mengen. Dabei bekommt jede Menge der Zerlegung ein kanonisches Element zugeordnet, welches als Name der Menge dient.
  • Étant donné un ensemble d'éléments, il est souvent utile de le partitionner en un certain nombre de classes disjointes, c'est-à-dire de représenter une relation d'équivalence.
  • L' MFSet (Merge-Find Set) è una struttura dati derivante dal concetto di Insieme delle parti, per cui dato un insieme finito di elementi a volte risulta utile partizionarli in insiemi disgiunti.
  • Struktura zbiorów rozłącznych to struktura danych, która przechowuje dla ustalonego zbioru (uniwersum) jego podział na mniejsze, rozłączne zbiory. Struktura taka umożliwia dwie operacje: Find: Wyznacza, w którym zbiorze jest dany element, pozwalając na sprawdzenie, czy dwa elementy są w tym samym zbiorze. Union: Łączy dwa zbiory w jeden. Czasem podaje się jeszcze trzecią operację, MakeSet, która dołącza do uniwersum nowy element jako jednoelementowy zbiór.
  • Система непересекающихся множеств позволяет администрировать множество элементов разбитое на непересекающиеся подмножества. При этом каждому подмножеству назначается его представитель — элемент этого подмножества.
  • 并查集是一种树型的数据结构，用于处理一些不相交集合（Disjoint Sets）的合并及查询问题。常常在使用中以森林来表示。
rdfs:label
  • Disjoint-set data structure
  • Union-Find-Struktur
  • Union-Find
  • Mfset
  • 素集合データ構造
  • Struktura zbiorów rozłącznych
  • Система непересекающихся множеств
  • 并查集
owl:sameAs
skos:subject
foaf:page
is dbpprop:redirect of
is owl:sameAs of