Disjoint-set data structure
http://dbpedia.org/resource/Disjoint-set_data_structure an entity of type: WikicatSearchAlgorithms
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.
rdf:langString
素集合データ構造（そしゅうごうデータこうぞう、英: 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つの代表を引数とする。
rdf:langString
Система непересекающихся множеств (англ. disjoint-set, или union–find data structure) — структура данных, которая позволяет администрировать множество элементов, разбитое на непересекающиеся подмножества. При этом каждому подмножеству назначается его представитель — элемент этого подмножества. Абстрактная структура данных определяется множеством трёх операций: . Применяется для хранения компонент связности в графах, в частности, алгоритму Краскала необходима подобная структура данных для эффективной реализации.
rdf:langString
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.
rdf:langString
在计算机科学中，并查集（英文：Disjoint-set data structure，直译为不交集数据结构）是一种数据结构，用于处理一些不交集（Disjoint sets，一系列没有重复元素的集合）的合并及查询问题。并查集支持如下操作：
* 查询：查询某个元素属于哪个集合，通常是返回集合内的一个“代表元素”。这个操作是为了判断两个元素是否在同一个集合之中。
* 合并：将两个集合合并为一个。
* 添加：添加一个新集合，其中有一个新元素。添加操作不如查询和合并操作重要，常常被忽略。 由于支持查询和合并这两种操作，并查集在英文中也被称为联合-查找数据结构（Union-find data structure）或者合并-查找集合（Merge-find set）。 “并查集”可以用来指代任何支持上述操作的数据结构，但是一般来说，“并查集”特指其中最常见的一种实现：不交集森林（Disjoint-set forest）。经过优化的不交集森林有线性的空间复杂度（，为元素数目，下同），以及接近常数的单次操作平均时间复杂度（，为反阿克曼函数），是效率最高的常见数据结构之一。 并查集是用于计算最小生成树的克鲁斯克尔演算法中的关键。由于最小生成树在网络路由等场景下十分重要，并查集也得到了广泛的引用。此外，并查集在符号计算，寄存器分配等方面也有应用。
rdf:langString
في علم الحاسوب، المجموعة المنفصلة من هيكلة البيانات كما تسمى ايضًا هيكلة بيانات العثور المتحد أو مجموعة العثور المندمج، هيكلة البيانات هذه تضمن أن يكون تتابع العناصر فيها منفصل في عدد من الفروع المفككة (غير متداخلة.) كما تدعم هذه الهيكلة عمليتان مفيدتين هما: 1- الإيجاد (Find) : تحديد في أي الفروع يوجد العنصر، تعيد عملية الإيجاد بالعادة العنصر من هذه المجموعة عن طريق ممثله عبر مقارنة نتيجتي علميتي بحث، ليتم تحديد إذا كان العنصرين في نفس المجموعة ام لا. 2- الاتحاد (Union) : حيث يقوم بجمع فرعين في فرع واحد.
rdf:langString
Στην πληροφορική, μια δομή ξένων συνόλων (Αγγλικά: disjoint-set data structure, γνωστή και ως union–find δομή ή σύνολο merge–find) είναι μια δομή δεδομένων η οποία χειρίζεται ένα σύνολο στοιχείων τα οποία διαχωρίζονται σε ένα αριθμό μη επικαλυπτόμενων υποσυνόλων (ή κλάσεων). Μια τέτοια δομή υποστηρίζει τις παρακάτω δύο βασικές λειτουργίες: Η βασική ιδέα είναι ότι ένα σύνολο "σύμπαν" διαμερίζεται σε υποσύνολα "κλάσεις" οι οποίες μεταβάλλοντα χρησιμοποιώντας την λειτουργία της ένωσης union.
rdf:langString
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.
rdf:langString
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.
rdf:langString
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.
rdf:langString
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
rdf:langString
컴퓨터 과학 분야에서 서로소 집합(disjoint-set) 자료 구조, 또는 합집합-찾기(union–find) 자료 구조, 병합-찾기 집합(merge–find set)은 많은 서로소 부분 집합들로 나눠진 원소들에 대한 정보를 저장하고 조작하는 자료 구조이다. 서로소 집합 자료 구조는 두 개의 유용한 연산을 제공한다:
* 파인드(Find): 어떤 원소가 주어졌을 때 이 원소가 속한 집합을 반환한다. 파인드는 일반적으로 어떤 원소가 속한 집합을 "대표" 하는 원소를 반환하는데, 이를 위하여 어떤 원소와 각 대표 원소들 간의 파인드 결과를 비교하여 같은 집합임을 판단한다.
* 유니온(Union): 두 개의 집합을 하나의 집합으로 합친다. 다른 중요한 연산으로 메이크셋(MakeSet)이 있으며 이는 특정 한 원소만을 가지는 집합을 만든다. 이 세 연산을 활용하여 많은 파티션(partitioning) 문제들을 해결할 수 있다. (응용 부분 참조)
rdf:langString
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.
rdf:langString
Система неперетинних множин (англ. disjoint-set-union або DSU, також використовують назви англ. union–find data structure, англ. merge–find set) — структура даних, яка дозволяє відстежувати множину елементів, розбиту на неперетинні підмножини. При цьому кожній підмножині призначається її представник — елемент цієї підмножини. Таким чином, базовий інтерфейс даної структури даних складається всього з трьох операцій: Описувана нижче структура даних дозволяє робити кожну з цих операцій майже за в середньому (більш докладно про асимптотику див. нижче після опису алгоритму).
rdf:langString
rdf:langString
هيكلة بيانات المجموعات المنفصلة
rdf:langString
Union-Find-Struktur
rdf:langString
Δομή ξένων συνόλων (πληροφορική)
rdf:langString
Estructura de datos para conjuntos disjuntos
rdf:langString
Disjoint-set data structure
rdf:langString
Union-find
rdf:langString
Mfset
rdf:langString
서로소 집합 자료 구조
rdf:langString
素集合データ構造
rdf:langString
Struktura zbiorów rozłącznych
rdf:langString
União-busca
rdf:langString
Система непересекающихся множеств
rdf:langString
Система неперетинних множин
rdf:langString
并查集
rdf:langString
Disjoint-set/Union-find Forest
xsd:integer
1037551
xsd:integer
1112375479
rdf:langString
multiway tree
rdf:langString
في علم الحاسوب، المجموعة المنفصلة من هيكلة البيانات كما تسمى ايضًا هيكلة بيانات العثور المتحد أو مجموعة العثور المندمج، هيكلة البيانات هذه تضمن أن يكون تتابع العناصر فيها منفصل في عدد من الفروع المفككة (غير متداخلة.) كما تدعم هذه الهيكلة عمليتان مفيدتين هما: 1- الإيجاد (Find) : تحديد في أي الفروع يوجد العنصر، تعيد عملية الإيجاد بالعادة العنصر من هذه المجموعة عن طريق ممثله عبر مقارنة نتيجتي علميتي بحث، ليتم تحديد إذا كان العنصرين في نفس المجموعة ام لا. 2- الاتحاد (Union) : حيث يقوم بجمع فرعين في فرع واحد. أما العملية المهمة الأخرى وهي صناعة المجموعة (MakeSet) والتي تصنع مجموعة تحتوي على عنصر واحد عديم الأهمية بالعادة. مع هذه العمليات الثلاث، يمكن حل العديد من مشاكل التقسيم العملية.) لكي يتم تحديد هذه العمليات بوضوح، يجب ان يكون هناك طريقة لتمثيل هذه البيانات، أحد هذه المناهج المتداول عليها هي اختيار عنصر ثابت من كل مجموعة يسمى الممثل، ليمثل المجموعة بأكملها.إذًا Find(x) تعيد ممثل المجموعة التي ينتمي اليها x، وعملية الاتحاد Union تأخد ممثلي المجموعتين لدمجهما معا في مجموعة واحدة.
rdf:langString
Στην πληροφορική, μια δομή ξένων συνόλων (Αγγλικά: disjoint-set data structure, γνωστή και ως union–find δομή ή σύνολο merge–find) είναι μια δομή δεδομένων η οποία χειρίζεται ένα σύνολο στοιχείων τα οποία διαχωρίζονται σε ένα αριθμό μη επικαλυπτόμενων υποσυνόλων (ή κλάσεων). Μια τέτοια δομή υποστηρίζει τις παρακάτω δύο βασικές λειτουργίες:
* Find (εύρεση): Καθορισμός σε ποιο υποσύνολο βρίσκεται ένα στοιχείο. Επιστρέφει ένα αντιπρόσωπο κλάσης που ανήκει το στοιχείο. Έχοντας δύο στοιχεία και χρησιμοποιώντας την λειτουργία find(x,y) σε δύο στοιχεία μπορούμε να δούμε αν τα δύο στοιχεία βρίσκονται στο ίδιο υποσύνολο / κλάση.
* Union (ένωση): Ένωση δύο υποσυνόλων/κλάσεων σε ένα υποσύνολο/κλάση. Η βασική ιδέα είναι ότι ένα σύνολο "σύμπαν" διαμερίζεται σε υποσύνολα "κλάσεις" οι οποίες μεταβάλλοντα χρησιμοποιώντας την λειτουργία της ένωσης union.
rdf:langString
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.
rdf:langString
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. While there are several ways of implementing disjoint-set data structures, in practice they are often identified with a particular implementation called a disjoint-set forest. This is a specialized type of forest which performs unions and finds in near-constant amortized time. To perform a sequence of m addition, union, or find operations on a disjoint-set forest with n nodes requires total time O(mα(n)), where α(n) is the extremely slow-growing inverse Ackermann function. Disjoint-set forests do not guarantee this performance on a per-operation basis. Individual union and find operations can take longer than a constant times α(n) time, but each operation causes the disjoint-set forest to adjust itself so that successive operations are faster. Disjoint-set forests are both asymptotically optimal and practically efficient. Disjoint-set data structures play a key role in Kruskal's algorithm for finding the minimum spanning tree of a graph. The importance of minimum spanning trees means that disjoint-set data structures underlie a wide variety of algorithms. In addition, disjoint-set data structures also have applications to symbolic computation, as well in compilers, especially for register allocation problems.
rdf:langString
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. La otra operación importante CrearConjunto es generalmente trivial, esta crea un conjunto con un elemento dado. Con estas tres operaciones, muchos problemas prácticos de particionamiento pueden ser resueltos(ver la sección de Aplicaciones). Con el fin de definir estas operaciones más precisamente , es necesario representar los conjuntos de alguna manera. Una aproximación común es seleccionar un elemento fijo de cada conjunto , llamado el representativo, para representar el conjunto como un todo. Entonces Buscar(x) retorna el elemento representativo del conjunto al cual x pertenece , y Unión toma como argumento dos elementos representivos de dos conjuntos respectivamente.
rdf:langString
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. 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 identifier la classe entière. Lors d'un appel, Find(x) retourne le représentant de la classe de x.
rdf:langString
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 L'altra operazione su MFSet è Crea, tramite la quale è possibile dato un insieme crearne la partizione formata solo da singoletti. Con l'utilizzo di questi tre operatori è possibile risolvere molti problemi pratici.
rdf:langString
컴퓨터 과학 분야에서 서로소 집합(disjoint-set) 자료 구조, 또는 합집합-찾기(union–find) 자료 구조, 병합-찾기 집합(merge–find set)은 많은 서로소 부분 집합들로 나눠진 원소들에 대한 정보를 저장하고 조작하는 자료 구조이다. 서로소 집합 자료 구조는 두 개의 유용한 연산을 제공한다:
* 파인드(Find): 어떤 원소가 주어졌을 때 이 원소가 속한 집합을 반환한다. 파인드는 일반적으로 어떤 원소가 속한 집합을 "대표" 하는 원소를 반환하는데, 이를 위하여 어떤 원소와 각 대표 원소들 간의 파인드 결과를 비교하여 같은 집합임을 판단한다.
* 유니온(Union): 두 개의 집합을 하나의 집합으로 합친다. 다른 중요한 연산으로 메이크셋(MakeSet)이 있으며 이는 특정 한 원소만을 가지는 집합을 만든다. 이 세 연산을 활용하여 많은 파티션(partitioning) 문제들을 해결할 수 있다. (응용 부분 참조) 위의 연산들을 정의하기 위하여 집합을 표현하는 방법이 필요하다. 일반적으로 각 집합 전체를 대표하는 하나의 고정된 대표 원소를 정하는 방법이 있다. 이 방법에서 파인드(x) 연산은 원소 x가 속한 집합의 대표 원소를 반환하고 유니온 연산은 두 대표 원소를 입력 인자로 사용한다.
rdf:langString
素集合データ構造（そしゅうごうデータこうぞう、英: 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つの代表を引数とする。
rdf:langString
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).
rdf:langString
Система непересекающихся множеств (англ. disjoint-set, или union–find data structure) — структура данных, которая позволяет администрировать множество элементов, разбитое на непересекающиеся подмножества. При этом каждому подмножеству назначается его представитель — элемент этого подмножества. Абстрактная структура данных определяется множеством трёх операций: . Применяется для хранения компонент связности в графах, в частности, алгоритму Краскала необходима подобная структура данных для эффективной реализации.
rdf:langString
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.
rdf:langString
Система неперетинних множин (англ. disjoint-set-union або DSU, також використовують назви англ. union–find data structure, англ. merge–find set) — структура даних, яка дозволяє відстежувати множину елементів, розбиту на неперетинні підмножини. При цьому кожній підмножині призначається її представник — елемент цієї підмножини. Структура даних надає такі можливості. Спочатку є кілька елементів, кожен з яких знаходиться в окремій (своїй власній) множині. За одну операцію можна об'єднати дві будь-які множини, а також можна запитати, в якій множині зараз знаходиться зазначений елемент. У класичному варіанті вводиться ще одна операція — створення нового елемента, який поміщається в окрему множину — синґлетон. Таким чином, базовий інтерфейс даної структури даних складається всього з трьох операцій:
* MakeSet — додання нового елемента; розміщення його в нову множину, що складається з одного нього;
* Union — об'єднання двох зазначених множин;
* Find — повернення значення, в якій множині знаходиться зазначений елемент. Насправді при цьому повертається один з елементів множини званий представником (англ. representative) або лідером (leader). Цей представник вибирається в кожній множині самою структурою даних (і може змінюватися з плином часу). Наприклад, якщо виклик для якихось двох елементів повернув одне і те ж значення, то це означає, що ці елементи знаходяться в одній і тій же множині, а в іншому випадку — в різних множинах. Описувана нижче структура даних дозволяє робити кожну з цих операцій майже за в середньому (більш докладно про асимптотику див. нижче після опису алгоритму). Також в одному з підрозділів статті описаний альтернативний варіант реалізації DSU, що дозволяє домогтися асимптотики в середньому на один запит.
rdf:langString
在计算机科学中，并查集（英文：Disjoint-set data structure，直译为不交集数据结构）是一种数据结构，用于处理一些不交集（Disjoint sets，一系列没有重复元素的集合）的合并及查询问题。并查集支持如下操作：
* 查询：查询某个元素属于哪个集合，通常是返回集合内的一个“代表元素”。这个操作是为了判断两个元素是否在同一个集合之中。
* 合并：将两个集合合并为一个。
* 添加：添加一个新集合，其中有一个新元素。添加操作不如查询和合并操作重要，常常被忽略。 由于支持查询和合并这两种操作，并查集在英文中也被称为联合-查找数据结构（Union-find data structure）或者合并-查找集合（Merge-find set）。 “并查集”可以用来指代任何支持上述操作的数据结构，但是一般来说，“并查集”特指其中最常见的一种实现：不交集森林（Disjoint-set forest）。经过优化的不交集森林有线性的空间复杂度（，为元素数目，下同），以及接近常数的单次操作平均时间复杂度（，为反阿克曼函数），是效率最高的常见数据结构之一。 并查集是用于计算最小生成树的克鲁斯克尔演算法中的关键。由于最小生成树在网络路由等场景下十分重要，并查集也得到了广泛的引用。此外，并查集在符号计算，寄存器分配等方面也有应用。
rdf:langString
Bernard A. Galler and Michael J. Fischer
xsd:integer
1964
xsd:nonNegativeInteger
31940
