Disjoint Set Data Structure – Union Find Algorithm

What is Disjoint-set data structure?

  • Represents a mathematics concept Set.
  • A disjoint-set data structure, also called a union–find data structure or merge–find set.
  • A disjoint-set data structure that keeps track of a set of elements partitioned into a number of disjoint or non-overlapping subsets.
  • It provides near-constant-time operations to add new sets, to merge existing sets, and to determine whether elements are in the same set.
  • Plays a key role in Kruskal’s algorithm for finding the minimum spanning tree of a graph.
  • This can also be used to detect cycle in the graph.

How Disjoint Set is constructed:

  • A disjoint-set forest consists of a number of elements each of which stores an id, a parent pointer
  • The parent pointers of elements are arranged to form one or more trees, each representing a set.
  • If an element’s parent pointer points to no other element, then the element is the root of a tree and is the representative member of its set.
  • A set may consist of only a single element. However, if the element has a parent, the element is part of whatever set is identified by following the chain of parents upwards until a representative element (one without a parent) is reached at the root of the tree.

Disjoint Set Operations:

MakeSet(X): This operation makes a new set by creating a new element with a parent pointer to itself. The parent pointer to itself indicates that the element is the representative member of its own set. The MakeSet operation has O(1) time complexity.

Find(X): follows the chain of parent pointers from x upwards through the tree until an element is reached whose parent is itself. This element is the root of the tree and is the representative member of the set to which x belongs, and may be x itself.

Union(x,y): Uses Find to determine the roots of the trees x and y belong to. If the roots are distinct, the trees are combined by attaching the root of one to the root of the other. If this is done naively, such as by always making x a child of y, the height of the trees can grow as O(n).

See the animation below for more understanding.

Arrow
Arrow
PlayPause
Slider

Code:

We can optimize this algorithm by doing “Union by rank and path compression”. Click here to read about it.

Applications using Disjoint sets:

  1. Represents network connectivity.
  2. Image Processing.
  3. In game algorithms.
  4. Kruskal’s minimum spanning tree.
  5. Find cycle in undirected graphs.

Ref: wiki

__________________________________________________
Top Companies Interview Questions..-

Google Microsoft Amazon Facebook more..

If you find anything incorrect or you feel that there is any better approach to solve the above problem, please write comment.
__________________________________________________

You may also like...

  • lipsa patel

    Why animation is not loading

    • tutorialhorizon

      Try in incognito, if it works in incognito then try clearing ur cache and reload the page. let us know if it is still not working

  • lipsa patel

    Was this question asked in any company interview?

    • tutorialhorizon

      Union – Find is a concept which us widely used in many problem solving like detect cycle in graph, krushkal algorithm etc. I will be posting articles (in next few days )which uses this concept. Thanks for following

  • lipsa patel

    “always making x a child of y” in Union operation should be
    “always making y a child of x”. This what is done in code.

%d bloggers like this: