Quick-Find Algorithm

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:

  1. Find: Check if p and q have same id
connected/find
id[0]=0 and id[6]=0, p and q are connected

2. Union: To merge components containing p and q, change all entries
whose id equals id[p] to id[q].

union
union(0,1) where id[p]=0 and id[q]=1

Lets take the following example for a better understanding.

Example output

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. 

Default step
assign id to the objects themselves

Next, we give various commands to form the connections.

  1. 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.
First step of connectivity
Array on first step of connectivity

2. Union(3,8) :  Both(refer to the above step) of those entries have to change to eight.

second step of connectivity
Array on second step of connectivity

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.

third step of connectivity
Array on third step of connectivity

4. Union(9,4) and Union(2,1)

fourth step of connectivity
Array on fourth step of connectivity
Union(2,1) is shown in lighter shade than union(9,4)

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)

sixth step of connectivity
Array on sixth step of connectivity

Implementation of the algorithm

We first create a public class and declare our data structure array, int id.

Create a constructor and two functions:

  1. QuickFindUF Constructor: To assign each object with its own id using a for loop
  2. connected() Function : Returns true or false based on p and q connectivity
  3. union(): To change id[p] to id[q] .i.e. second id to first as we did in the above example.
Java implementation

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.

We will be happy to hear your thoughts

Leave a reply

Edusera
Logo
Open chat
1
Scan the code
Hello!👋
Can we help you?