A Union-Find Algorithm
The first implementation of an algorithm for solving the dynamic connectivity problem, called Quick-find.
It is also called as eager algorithm, for solving kind activity problem.
The data structure that we’re going to use to support the algorithm is simply an integer array indexed by object.
P and Q are connected if they have the same entries the array.
So there are two key steps in this:
- Find: Check if p and q have same id
2. Union: To merge components containing p and q, change all entries
whose id equals id[p] to id[q].
Lets take the following example for a better understanding.
To get the connections between the given objects in the above picture,
First, we must form connections with the objects themselves .i.e. assign them as their own ids. by initially, setting up the ID array, with each entry, equal to its index.
Next, we give various commands to form the connections.
- Union(4,3) : We’re going to change, all entries, whose ID is equal to the first ID to the second one. So in this case, we’ll change the, connect three and four means that we need to change the four to a three.
2. Union(3,8) : Both(refer to the above step) of those entries have to change to eight.
3. Union(6,5) : Again, we change the first one to match the second one. So to connect six and five, we change the six to a five.
4. Union(9,4) and Union(2,1)
5. If the user inputs connected(8,9) then function returns true (already connected through 3 and 4) and on inputting connected(5,0) it returns false.
6. Union(5,0), Union(7,2) and Union(6,1)
Implementation of the algorithm
We first create a public class and declare our data structure array, int id.
Create a constructor and two functions:
- QuickFindUF Constructor: To assign each object with its own id using a for loop
- connected() Function : Returns true or false based on p and q connectivity
- union(): To change id[p] to id[q] .i.e. second id to first as we did in the above example.
Quick-Find algorithm is quick, although to check array entries a constant number of times, is problematic making the union operation too expensive and less efficient.
