Disjoint-set data structure is very useful data structure which keeps track of collection of items and its set, i.e which item belongs to which set. it is also called union-find data structure.

disjoint set data structure c++Here we can see four sets and its members. a set is a collection of objects. Assume 1,2,3,4,5,6,7,8,9,10,11,12 to be items. In each set the connection between items shows pair wise relation. For example in set 3 the line between 8 to 9 shows relation between 8 and 9, the relation can be interpreted as an edge of a tree. Note that the divided groups of items ( set1,set2,set3,set4) does not overlap. i.e no two or more sets have common item.

Disjoint Set Operations:

  1.   find() – Determine which set an item belongs to.
  2.   union() – Combine or merge two sets into a single set.

A simple array implementation of disjoint-data structure ( union-find algorithm)

unfLet left side tree is set A and right side tree is set B. A = { 1,2,3,5} and B = { 4,0,6}. The set A can be uniquely identified by  1 which is root of  set A and same as set B can be uniquely identified by  4 which is root of  set B. if  we take an array of length ( total number of items ) and initially assigned each element of array to its index value, then this will represents sparse items. now if we assign ith parent’s node to its ith index then we can easily identified which elements belongs to which sets by getting its root node because root node identifies the sets. like below

//find(int i) – Determine which set an item belongs to.

Alright we have learn disjoint-set data structure simple implementation. Let us use this DS to detect cycle in connected weighted graph.

mstkdisjoint set data structure c++


Related Contents to follow