Introduction

Hey there, folks! Today, we're going to dive into the wild world of algorithms! Yeah, I know, it sounds as exciting as watching paint dry, but stick with me because I've got a tale to tell. It's an algorithm; don't just read about it, code it out as you go, then it will make sense.

So what is it, really?

The Union-Find algorithm is used to manage disjoint sets, and that's why it's also known as the Disjoint Set algorithm. You can efficiently find which set an element belongs to. For example, in the image 2 below, element 2 belongs to the first set, and element 4 belongs to the second set.

You can also use it to find if the graph forms a cycle or not. Like in image 2, the second graph below forms a cycle, but the first one does not.

As the name suggests, the Union-Find algorithm has two main operations:

• Find: This operation determines which set a particular element belongs to. It typically returns a representative element for the set, i.e. the parent/root of that set.
• Union: This operation merges two sets into one. It takes two elements from different sets and combines them.

The example

The example we're dissecting today is this: given 6 vertices (0, 1, 2, 3, 4, 5) and 5 edges [0,1] [0,2] [3,5] [3,4] [5,4], figure out two things, first, if the graph has a cycle and second, if a path exists between 0 & 3.

So, we've got 6 vertices in total: 0, 1, 2, 3, 4, 5.

Image 1: 6 vertices

And we also have edges = [0,1] [0,2] [3,5] [3,4] [5,4], which makes our final graph look like this:

Image 2: The final graph

That's good for visual understanding, but how do we <code> it out to make it actually work right?

Class UnionFind

Let's start by simply creating a UnionFind Class with a parent[ ] array. Now, the index of the parent array represents the vertices (0,1,2,3,4,5), and the value of the array represents the parent each vertex belongs to.

public class UnionFind {
    private int[] parent;
}

Listing 1. Class UnionFind

When we start, we have no idea which vertex belongs to which set. Hence, initially, each vertex is its own parent. This means the index of an array will be the value of the array, too. We can initialize the array in a constructor, which takes n (the number of vertices), 6 in our example, as a parameter. To set each vertex to be its own parent initially, just run through a for loop as follows:

// Parent[6] array with 6 elements
// Values [0 1 2 3 4 5]
// Index   0 1 2 3 4 5

public UnionFind(int n) 
{
    parent = new int[n];
    for (int i = 0; i < n; i++)
         parent[i] = i;
}

Listing 2. The constructor of the class UnionFind

Now your set, or should I call them {sets}, looks like this:

Image 3: Each vertex belongs to a separate set

The Find Operation

To demonstrate the workings of the Find operation, let's consider the following example. It is in different color blue than other images because this is not same as our original example.

Image 4: Alternate example to explain the workings of the find operation

This is what the code for the Find operation looks like:

public int Find(int x) 
{
   if (parent[x] == x)
       return x;
   return parent[x] = Find(parent[x]);
}

Listing 3: The Find method

Explanation: We recursively find the root of each vertex. In the above image 4, if you pass vertex 3, it recursively calls vertex 2, then it calls its parent i.e. vertex 0. Now, once you reach the root, you hit the base condition where we realize vertex 0 is the parent of itself, so we return that.

The Union Operation

The Union(int x, int y) method is used to merge the sets containing vertices x and y. First, it finds the root of x, then finds the root of y using the Find operation. If the parent of both of these vertices are not the same, meaning these 2 vertices (x and y) belong to a different set, so we go ahead and merge them together.