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.
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…
View original post 43 more words