The pair of operations, union and find, that operate on a disjoint-set data structure, used with path compression and union by rank to answer connectivity queries and merge groups in nearly constant amortized time.
Facts
Core PrincipleProvides operations for adding new sets, merging sets, and finding a representative member of a set. 1 Connections
Sources
1. Disjoint-set data structure, Wikipedia
History
Disjoint-set forests were first described by Bernard A. Galler and Michael J. Fischer in 1964.
Core Functionality
It provides operations for adding new sets, merging sets (replacing them with their union), and finding a representative member of a set.
View the SourceFrequently Asked Questions
Who first described the disjoint-set forests that the union-find algorithm relies on?
Bernard A. Galler and Michael J. Fischer first described disjoint-set forests in 1964.
Disjoint-set forests, the data structure behind the union-find algorithm, were first described by Bernard A. Galler and Michael J. Fischer in 1964.
Reader Challenges (0)
No disputes yet. Spotted an error or a better source? Open the first one.
Sign in to dispute this or suggest a correction.