Introduction to Disjoint Set (Union-Find Algorithm) Using Python

The most basic data structure in the field of computer science, the disjoint set, also goes by the name Union-Find method and effectively handles splitting components into disjoint sets. This approach is quite helpful when it comes to handling difficulties involving connection and equivalency relationships. Implementing Kruskal's approach to determine a graph's minimum spanning tree is one of its frequently used applications.

This essay will thoroughly explore Disjoint Set, covering its applications, usage, and Python implementation.

Basics of Disjoint Set

Data structures that enable the grouping of components into non-overlapping groups are known as disjoint set data structures. It keeps track of a set of disjoint sets, with a representative element-also referred to as the root element-in each set. A set can be recognised and distinguished from other sets using its root element.

Several important operations are supported by the disjoint set data structure, including creating new sets, merging existing sets, and determining a set's root element. Because these operations can be completed quickly, even on sizable sets, the disjoint set data structure is appropriate for various uses.

Managing the division of components into disjoint sets is the function of the disjoint set. The idea that every set has a representative element is crucial because it makes it easier to determine the relationships of equivalency and connection between elements. Disjoint Set primarily supports the following operations: Union, Find, and MakeSet.

The following are the main ideas of a disjoint set:

• MakeSet(x): Constructs a new set with element x in it.
• Union(x, y): Creates a single set by combining the sets that contain elements x and y.
• Find(x): Gives back the set's representative element that contains x.

Just initialise a new element and designate it as the representative element of its own set to create a new set. Determine each set's root elements, then designate one root element as the parent of the other set to combine the two. A set's root element can be located by following the parent pointer chain until you come to an element that points to itself.

How to Create Disjoint Sets?

Sets will be referred to as disjoint sets if they lack common items, i.e., the intersection set is null. The purpose of a Disjoint Set is to effectively manage the division of elements into disjoint sets, with a representative element in each set. The primary objective is efficiently carrying out tasks like combining two sets or determining whether two components are part of the same set.

The Disjoint carries out the following functions set data structure:

• New sets added to the disjoint set
• Union operation merges disparate sets into a single disjoint set.
• Using the Find the procedure and determine the representative of a disjoint set.
• Verify whether two sets are disjoint.

Components of Disjoint Set

1. Parent Array: Each element in the disjoint sets has a parent element, which is maintained by the parent array, which is the central component of the disjoint set. Each element is initialised as its parent, resulting in the formation of singleton sets.
2. Rank Array: In order to optimise the Union process, the rank array is essential. In order to maintain a balanced structure and stop the growth of unduly tall trees, the rank array is employed to store each node's rank and monitor each tree's depth.

This Python code snippet can be used to define the parent array and rank array:

A class Disjoint( ) is made in which the parent and rank array are defined.

Operations on Disjoint Set

1. Makeset(x)

The first step in using the Disjoint Set is to perform the MakeSet operation. It creates a set with just one element, x. This entails initialising the rank to 0 and setting the parent of x to itself.

2. Find(x)

A key component of the Disjoint Set is the Find operation, which finds the root, or representative element, of the set that contains element x. Path compression (flattening the tree structure) is used to optimise Find operations in the future.

3. Union(x)

The sets that include elements x and y are combined using the Union procedure. In order to create a balanced and effective structure, it uses the ranks to join the tree with the lesser depth to the tree with the bigger depth.

Comprising all the structures and operations, this is how a disjoint set works:

Example of Disjoint Set in Python

The following code gives an example explaining the working of the disjoint set.

Output:

 1 

A Separate make_set function is used to build sets for each element from 0 to 5 after the set is initialised with a size of 6. Then, sets including elements 0, 2, 1, 3, and 4 are subjected to union operations. In order to identify the representative element of the set that contains element 1, the find method is finally invoked. Next, sets are made for the first five elements. The sets comprising items 0 and 2 are combined in the first union operation. The sets comprising items 1 and 3 are combined in the second union operation. The sets containing items 1 and 0 are combined in the third union operation. The sets comprising items 3 and 4 are combined in the fourth union operation. The elements 0 through 3 belong to the same set.

Applications of Disjoint Set

The Disjoint Set has been used in various domains and subfields. Some of the most widely utilised uses are as follows:

• Kruskal's Algorithm: This technique for determining a graph's lowest spanning tree frequently uses disjoint sets.
• linked Components: In graph theory, an undirected graph's linked components are found using a disjoint set.
• Dynamic Connectivity: It is used in situations involving elements that are added or removed and the efficient updating of connectivity information.

Conclusion

The Union-Find set of rules allows for implementing the Disjoint Set information shape, a beneficial device for graph algorithms and dynamic connectivity issues. Because route compression and union via rank are enormously efficient and might do fundamental operations in almost steady time, comprehending and executing this algorithm is vital for addressing an in-depth array of computer science know-how troubles.