What is a disjoint set in data structure?

Software Development
,
#1

Two sets are called disjoint sets if they don’t have any element in common, the intersection of sets is a null set.

A data structure that stores non overlapping or disjoint subset of elements is called disjoint set data structure. The disjoint set data structure supports following operations:

  • Adding new sets to the a disjoint set.
  • Merging disjoint sets to a single disjoint set using Union operation.
  • Finding representative of a disjoint set using Find operation.
  • Check if two sets are disjoint or not.

Consider a situation with a number of persons and the following tasks to be performed on them:

  • Add a new friendship relation, i.e. a person x becomes the friend of another person y i.e adding new element to a set.
  • Find whether individual x is a friend of individual y (direct or indirect friend)

Examples:

We are given 10 individuals say, a, b, c, d, e, f, g, h, i, j
Following are relationships to be added:
a <-> b 
b <-> d
c <-> f
c <-> i
j <-> e
g <-> j
Given queries like whether a is a friend of d or not. We basically need to create following 4 groups and maintain a quickly accessible connection among group items:
G1 = {a, b, d}
G2 = {c, f, i}
G3 = {e, g, j}
G4 = {h}

Find whether x and y belong to the same group or not, i.e. to find if x and y are direct/indirect friends.

Partitioning the individuals into different sets according to the groups in which they fall. This method is known as a Disjoint set Union which maintains a collection of Disjoint sets and each set is represented by one of its members