A disjoint-set data structure is a collection of non-overlapping sets that provides operations for adding new sets, merging sets, and finding a representative member of a set. It is often implemented as a disjoint-set forest which performs unions and finds in near-constant amortized time. Disjoint-set data structures are used in Kruskal's algorithm and have applications to symbolic computation and compilers.
Princeton University
Spring 2023
This course surveys crucial algorithms and data structures used in modern computing, with emphasis on sorting, searching, graphs, and strings. It aims to develop implementations, understand their performance, and evaluate their effectiveness.
No concepts data
+ 25 more concepts