Disjoint-set data structure

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 as in compilers, especially for register allocation problems. Disjoint-set forests were first described by Bernard A. Galler and Michael J. Fischer in 1964. In 1973, their time complexity was bounded to , the iterated logarithm of , by Hopcroft and Ullman. In 1975, Robert Tarjan was the first to prove the (inverse Ackermann function) upper bound on the algorithm's time complexity,.

About this result

This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.

Related publications (40)

Related people (4)

Related units (4)

Related concepts (5)

Related courses (14)

Related lectures (34)

Sketches, metrics and fast algorithms

Navid Nouri

As it has become easier and cheaper to collect big datasets in the last few decades, designing efficient and low-cost algorithms for these datasets has attracted unprecedented attention. However, in most applications, even storing datasets as acquired has ...

EPFL2022

Promoting Connectivity of Network-Like Structures by Enforcing Region Separation

Pascal Fua, Doruk Oner, Mateusz Kozinski, Leonardo Citraro

We propose a novel, connectivity-oriented loss function for training deep convolutional networks to reconstruct network-like structures, like roads and irrigation canals, from aerial images. The main idea behind our loss is to express the connectivity of r ...

2021

Large-Scale Crowdsourcing Subjective Quality Evaluation of Learning-Based Image Coding

Touradj Ebrahimi, Evgeniy Upenik, Michela Testolina

Learning-based image codecs produce different compression artifacts, when compared to the blocking and blurring degradation introduced by conventional image codecs, such as JPEG, JPEG~2000 and HEIC. In this paper, a crowdsourcing based subjective quality e ...

IEEE2021

MATH-106(f): Analysis II

Étudier les concepts fondamentaux d'analyse et le calcul différentiel et intégral des fonctions réelles de plusieurs variables.

MATH-203(b): Analysis III

Le cours étudie les concepts fondamentaux de l'analyse vectorielle et l'analyse de Fourier en vue de leur utilisation pour résoudre des problèmes pluridisciplinaires d'ingénierie scientifique.

MATH-203(c): Analysis III

Le cours étudie les concepts fondamentaux de l'analyse vectorielle et l'analyse de Fourier en vue de leur utilisation pour résoudre des problèmes pluridisciplinaires d'ingénierie scientifique.

Connectivity (graph theory)

In mathematics and computer science, connectivity is one of the basic concepts of graph theory: it asks for the minimum number of elements (nodes or edges) that need to be removed to separate the remaining nodes into two or more isolated subgraphs. It is closely related to the theory of network flow problems. The connectivity of a graph is an important measure of its resilience as a network. In an undirected graph G, two vertices u and v are called connected if G contains a path from u to v.

Partition of a set

In mathematics, a partition of a set is a grouping of its elements into non-empty subsets, in such a way that every element is included in exactly one subset. Every equivalence relation on a set defines a partition of this set, and every partition defines an equivalence relation. A set equipped with an equivalence relation or a partition is sometimes called a setoid, typically in type theory and proof theory. A partition of a set X is a set of non-empty subsets of X such that every element x in X is in exactly one of these subsets (i.

Minimum spanning tree

A minimum spanning tree (MST) or minimum weight spanning tree is a subset of the edges of a connected, edge-weighted undirected graph that connects all the vertices together, without any cycles and with the minimum possible total edge weight. That is, it is a spanning tree whose sum of edge weights is as small as possible. More generally, any edge-weighted undirected graph (not necessarily connected) has a minimum spanning forest, which is a union of the minimum spanning trees for its connected components.

Max-flow and Disjoint Sets CS-250: Algorithms I

Explores the Ford-Fulkerson method, max-flow, applications of max-flow, and the disjoint-set data structure.

Field Derivation: Potential and Convexity MATH-203(b): Analysis III

Covers the derivation of a field from a potential and explores convexity.

Introduction to Partial Differential Equations MATH-351: Advanced numerical analysis

Covers the basics of Partial Differential Equations, focusing on heat transfer modeling and numerical solution methods.