You are required to implement correctly and efficiently the base operations for disjoint set
(chapter 21.1 from book ) and the Kruskal’s algorithm (searching for the minimum spanning tree - chapter 23.2) using disjoint sets.
You have to use a tree as the representation of a disjoint set. Each tree holds, besides the necessary information, also the rank field (i.e. the height of the tree).
The base operations on disjoints sets are:
● MAKE_SET (x)
○ creates a set with the element x
● UNION (x, y)
○ makes the union between the set that contains the element x and the set that contains the element y
○ the heuristic union by rank takes into account the height of the two trees so as to make the union
○ the pseudo-code can be found in the chapter 21.3 from the book[1]
● FIND_SET (x)
○ searches for the set that contains the element x
○ the heuristic path compression links all nodes that were found on the path to x to the root node
Thresholds
