| rdfs:comment
| - 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 disjunkte 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 Elementarmenge {x} mit dem kanonischen Element x. (de)
- 素集合データ構造（そしゅうごうデータこうぞう、英: 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つの代表を引数とする。 (ja)
- Система непересекающихся множеств (англ. disjoint-set, или union–find data structure) — структура данных, которая позволяет администрировать множество элементов, разбитое на непересекающиеся подмножества. При этом каждому подмножеству назначается его представитель — элемент этого подмножества. Абстрактная структура данных определяется множеством трёх операций: . Применяется для хранения компонент связности в графах, в частности, алгоритму Краскала необходима подобная структура данных для эффективной реализации. (ru)
- Em ciência da computação, uma estrutura de dados união-busca também chamado de estrutura de dados disjoint-set é uma estrutura de dados que mantém o controle de um conjunto de elementos particionados em subconjuntos disjuntos (não sobreposicionados). Ele fornece operações com tempo quase constante (delimitadas pela inversa função de Ackermann) para adicionar novos conjuntos, para mesclar conjuntos existentes e para determinar se os elementos estão no mesmo conjunto. Além de muitos outros usos, os disjoint-sets desempenham um papel fundamental no algoritmo de Kruskal para encontrar a árvore de extensão mínima em um grafo. (pt)
- 在计算机科学中，并查集（英文：Disjoint-set data structure，直译为不交集数据结构）是一种数据结构，用于处理一些不交集（Disjoint sets，一系列没有重复元素的集合）的合并及查询问题。并查集支持如下操作：
* 查询：查询某个元素属于哪个集合，通常是返回集合内的一个“代表元素”。这个操作是为了判断两个元素是否在同一个集合之中。
* 合并：将两个集合合并为一个。
* 添加：添加一个新集合，其中有一个新元素。添加操作不如查询和合并操作重要，常常被忽略。 由于支持查询和合并这两种操作，并查集在英文中也被称为联合-查找数据结构（Union-find data structure）或者合并-查找集合（Merge-find set）。 “并查集”可以用来指代任何支持上述操作的数据结构，但是一般来说，“并查集”特指其中最常见的一种实现：不交集森林（Disjoint-set forest）。经过优化的不交集森林有线性的空间复杂度（，为元素数目，下同），以及接近常数的单次操作平均时间复杂度（，为反阿克曼函数），是效率最高的常见数据结构之一。 并查集是用于计算最小生成树的克鲁斯克尔演算法中的关键。由于最小生成树在网络路由等场景下十分重要，并查集也得到了广泛的引用。此外，并查集在符号计算，寄存器分配等方面也有应用。 (zh)
- في علم الحاسوب، المجموعة المنفصلة من هيكلة البيانات كما تسمى ايضًا هيكلة بيانات العثور المتحد أو مجموعة العثور المندمج، هيكلة البيانات هذه تضمن أن يكون تتابع العناصر فيها منفصل في عدد من الفروع المفككة (غير متداخلة.) كما تدعم هذه الهيكلة عمليتان مفيدتين هما: 1- الإيجاد (Find) : تحديد في أي الفروع يوجد العنصر، تعيد عملية الإيجاد بالعادة العنصر من هذه المجموعة عن طريق ممثله عبر مقارنة نتيجتي علميتي بحث، ليتم تحديد إذا كان العنصرين في نفس المجموعة ام لا. 2- الاتحاد (Union) : حيث يقوم بجمع فرعين في فرع واحد. (ar)
- Στην πληροφορική, μια δομή ξένων συνόλων (Αγγλικά: disjoint-set data structure, γνωστή και ως union–find δομή ή σύνολο merge–find) είναι μια δομή δεδομένων η οποία χειρίζεται ένα σύνολο στοιχείων τα οποία διαχωρίζονται σε ένα αριθμό μη επικαλυπτόμενων υποσυνόλων (ή κλάσεων). Μια τέτοια δομή υποστηρίζει τις παρακάτω δύο βασικές λειτουργίες: Η βασική ιδέα είναι ότι ένα σύνολο "σύμπαν" διαμερίζεται σε υποσύνολα "κλάσεις" οι οποίες μεταβάλλοντα χρησιμοποιώντας την λειτουργία της ένωσης union. (el)
- In computer science, a disjoint-set data structure, also called a union–find data structure or merge–find set, is a data structure that stores a collection of disjoint (non-overlapping) sets. Equivalently, it stores a partition of a set into disjoint subsets. It provides operations for adding new sets, merging sets (replacing them by their union), and finding a representative member of a set. The last operation makes it possible to find out efficiently if any two elements are in the same or different sets. (en)
- En computación, una estructura de datos para conjuntos disjuntos, es una estructura de datos que mantiene un conjunto de elementos particionados en un número de conjuntos disjuntos(no se solapan los conjuntos).Un algoritmo Unión-Buscar es un algoritmo que realiza dos importantes operaciones en esta estructura de datos:
* Buscar: Determina a cual subconjunto pertenece un elemento. Esta operación puede usarse para verificar si dos elementos están en el mismo conjunto.
* Union: Une dos subconjuntos en uno solo. (es)
- En informatique, union-find est une structure de données qui représente une partition d'un ensemble fini (ou de manière équivalente une relation d'équivalence).Elle a essentiellement deux opérations trouver et unir et est appelée union-find, suivant en cela la terminologie anglo-saxonne :
* Find (trouver) : détermine la classe d'équivalence d'un élément ; elle sert ainsi à déterminer si deux éléments appartiennent à la même classe d'équivalence ;
* Union (unir) : réunit deux classes d'équivalence en une seule. Lors d'un appel, Find(x) retourne le représentant de la classe de x. (fr)
- L'MFSet (Merge-Find Set), altrimenti conosciuto come struttura dati union-find, è una struttura dati derivante dal concetto di partizione, per cui dato un insieme finito di elementi a volte risulta utile partizionarli in insiemi disgiunti. L'algoritmo di Merge-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 (it)
- 컴퓨터 과학 분야에서 서로소 집합(disjoint-set) 자료 구조, 또는 합집합-찾기(union–find) 자료 구조, 병합-찾기 집합(merge–find set)은 많은 서로소 부분 집합들로 나눠진 원소들에 대한 정보를 저장하고 조작하는 자료 구조이다. 서로소 집합 자료 구조는 두 개의 유용한 연산을 제공한다:
* 파인드(Find): 어떤 원소가 주어졌을 때 이 원소가 속한 집합을 반환한다. 파인드는 일반적으로 어떤 원소가 속한 집합을 "대표" 하는 원소를 반환하는데, 이를 위하여 어떤 원소와 각 대표 원소들 간의 파인드 결과를 비교하여 같은 집합임을 판단한다.
* 유니온(Union): 두 개의 집합을 하나의 집합으로 합친다. 다른 중요한 연산으로 메이크셋(MakeSet)이 있으며 이는 특정 한 원소만을 가지는 집합을 만든다. 이 세 연산을 활용하여 많은 파티션(partitioning) 문제들을 해결할 수 있다. (응용 부분 참조) (ko)
- 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. (pl)
- Система неперетинних множин (англ. disjoint-set-union або DSU, також використовують назви англ. union–find data structure, англ. merge–find set) — структура даних, яка дозволяє відстежувати множину елементів, розбиту на неперетинні підмножини. При цьому кожній підмножині призначається її представник — елемент цієї підмножини. Таким чином, базовий інтерфейс даної структури даних складається всього з трьох операцій: Описувана нижче структура даних дозволяє робити кожну з цих операцій майже за в середньому (більш докладно про асимптотику див. нижче після опису алгоритму). (uk)
|
_Union_Find.jpg)
![[RDF Data]](/fct/images/sw-rdf-blue.png)
![[cxml]](/fct/images/cxml_doc.png)
![[csv]](/fct/images/csv_doc.png)
![[text]](/fct/images/ntriples_doc.png)
![[turtle]](/fct/images/n3turtle_doc.png)
![[ld+json]](/fct/images/jsonld_doc.png)
![[rdf+json]](/fct/images/json_doc.png)
![[rdf+xml]](/fct/images/xml_doc.png)
![[atom+xml]](/fct/images/atom_doc.png)
![[html]](/fct/images/html_doc.png)