A structure, also called a union-find structure, that tracks a collection of elements partitioned into non-overlapping sets and supports quickly finding which set an element belongs to and merging two sets together; central to Kruskal's algorithm and to cycle detection.
Facts
Core Principlea 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 1 Connections
Sources
1. Disjoint-set data structure, Wikipedia
Lead section
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
History section
Disjoint-set forests were first described by Bernard A. Galler and Michael J. Fischer in 1964.
View the SourceFrequently Asked Questions
Who first described the disjoint-set data structure?
First described by Bernard A. Galler and Michael J. Fischer in 1964.
Disjoint-set forests were first described by Bernard A. Galler and Michael J. Fischer in 1964. The structure has been in use since that founding work to track partitioned collections of elements and to merge sets efficiently.
Why is a disjoint-set structure also called union-find?
Its two core operations are find and union, so it is also called union-find.
A disjoint-set data structure is also called a union-find data structure or merge-find set because its two defining operations are finding which set an element belongs to and merging two sets together. The alternate names describe those operations directly rather than the partitioned collection itself.
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.