Disjoint Set meaning and definition in DSA

Disjoint Set is a data structure that keeps track of a set of elements partitioned into a number of disjoint subsets and it is used to efficiently solve problems that involve grouping elements into sets and performing operations on them.

Characteristics of  the Disjoint Set:

• It keeps a set partitioned into disjoint subsets.
• It allows the efficient union of two subsets.
• It makes it possible to quickly determine a given element belongs to which subset.

How to identify a Disjoint set:

To identify a disjoint set look for the following points in the set:

• In the Disjoint set, each element in a set is represented by a unique root node.
• In the Disjoint set, two elements belong to the same set if they share the same root node.
• The root node of an element can be found by following the parent pointers until a node is reached that has itself as its parent.

Application of Disjoint set

• Kruskal’s algorithm: Kruskal’s algorithm uses the disjoint set data structure to efficiently determine the minimum spanning tree of a graph.
• Union-find algorithms: The disjoint set data structure is often used in union-find algorithms to efficiently perform union and find operations on sets of data elements.
• Computer networks: The disjoint set data structure can be used to keep track of the network components and to detect network failures.
• Cycle Detection in a Graph: Disjoint Set is used to detect cycle in an undirected graph.

What else can you read?

• Disjoint Set Union on Trees
• Union-find algorithm
• Kruskal’s Minimum Spanning Tree (MST) Algorithm

Commit to GfG’s Three-90 Challenge! Purchase a course, complete 90% in 90 days, and save 90% cost click here to explore.