Be the first user to complete this post

  • 0
 Add to List
Hard

278. Disjoint Set Data Structure - Union Find Algorithm

What is Disjoint-set data structure?

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

How Disjoint Set is constructed:

  1. A disjoint-set forest consists of a number of elements each of which stores an id, a parent pointer
  2. The parent pointers of elements are arranged to form one or more trees, each representing a set.
  3. 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.
  4. 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.

Output:

Set Id: 0 elements: [0, 1, 2, 3]
Set Id: 4 elements: [4, 5]

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

Related Problems: