A disjoint-set data structure, also called a union–find data structure keeps track of a set of elements partitioned into a number of disjoint (non-overlapping) subsets. With this setting we define the following operations:
Find: Determine which subset a particular element is in. This can be used for determining if two elements are in the same subset.
Union: Join two subsets into a single subset.
To be more specific, Union(x, y): replaces the set x and set y with a single set x U y. Find(x): returns the unique ID for the set containing x.
Example Usage:
The data structure can be used in Kruskal’s algorithm. Kurskal’s algorithm to find the minimum spanning tree first sorts all the edges and then adds them one by one to the tree taking care that no cycle is formed.
When we consider an edge (v, w) in the algorithm, we just test whether Find(v) equals Find(w). If they are equal, it means that v and w are already in the same tree so we skip over the edge. If they are not equal, we insert the edge into our forest and perform a Union(v, w) operation.
Reblogged this on PH Bytes.
LikeLike