I decided to write a series of articles on Union Find algorithms. Though there are other resources available online. Lots of blogs, articles, books are out there on this topic. I just thought, I could make it easy to understand. These are for the beginner level programmers. But basic understanding of programming and Object Oriented Programming is required. Quick find algorithm is the basic one. This will give a preliminary idea of the Union Find algorithm. And then slowly we will dive into the complexity.
Problem
The goal of this algorithm is to find if any two elements are connected. If not connected, then connect them. This problem is also called dynamic connectivity problem. This connection is an equivalence relationship. We assume that:
- Symmetric: If p is connected to q, then q is also connected to p.
- Transitive: If p is connected to q and q is connected to r, p is connected to r as well.
- Reflexive: p is connected to p.
Applications
These types of algorithms help manipulating the objects of all types:
Computers in a network
Elements in a mathematical set
Metallic sites in a composite system
Pixels in a digital photo
Friends in a social network
Transistors in a computer chip
Variable names in Fortran program
Solution
Before starting the coding challenge, align the steps in order. These are the steps to develop an efficient algorithm:
Model the problem
Find an algorithm to solve it
Check if the algorithm is fast enough and the memory usage
If not fast enough, figure out why
Find a way to address the problem
Keep doing the same process until it satisfies the requirement
Model of the Quick Find algorithm:
This quick find algorithm is called eager algorithm to solve so called dynamic connectivity problem. The structure of the data includes an integer array id[] of size N. N is any integer. Integer array id[] is supposed to be a range from 0 to N-1. p and q are 2 integers in the id array. p and q are connected if they have the same id.
I will implement this algorithm in Java and Python. These are the steps we will follow to develop this structure.
Step 1:
We need to develop a constructor first giving an input N. N is the size of the data as I mentioned earlier. I am putting the name of the constructor as QuickFind. In this constructor first we will generate an array of range N. Each element is an id that is the same as the element position starting from 0. Such as id of position 1 is 1, id of position 0 is 0, id of position 7 is 7.
Step 2:
Develop a class ‘connect’ that takes two inputs p and q. It returns a Boolean that indicates if they are already connected. If this class returns yes, then the algorithm doesn’t do anything. But if it returns no, then the algorithm implements the union operation that connects p and q.
Step 3:
Develop a class named ‘union’ that connects p and q. Iterate through the array id. Where you find the id of p, change it to id of q.
Example of Union operation:
Here is our id array. We are taking a range from 0 to 8.
0 1 2 3 4 5 6 7 8
Id 0 1 2 3 4 5 6 7 8
Union (3, 4):
Change the id of 3 to id of 4.
0 1 2 3 4 5 6 7 8
Id 0 1 2 4 4 5 6 7 8
Union (3, 8):
Replace id of 3 with id of 8. As I described in the step 3 above, we need to iterate through the id array and wherever we find an id that is the same as the id of 3 we need to change that to id of 8
0 1 2 3 4 5 6 7 8
Id 0 1 2 8 8 5 6 7 8
Union (5, 6):
This one will be the same as the first one.
0 1 2 3 4 5 6 7 8
Id 0 1 2 8 8 6 6 7 8
Union (4, 6):
0 1 2 3 4 5 6 7 8
Id 0 1 2 6 6 6 6 7 6
Java Implementation:
public class QuickFind {
private int[] id;
public QuickFind(int N) {
id = new int[N];
for (int i=0; i<N; i++) {
id[i] = i;
}
}
private boolean connected(int p, int q) {
return id[p] == id[q];
}
public void union(int p, int q) {
int pid = id[p];
int qid = id[q];
for (int i=0; i<id.length; i++) {
if (id[i]==pid) id[i] = qid;
}
}
}
Python Implementation
class QuickFind(object):
def __init__(self, N):
self.lst = list(range(N))
def find(self, p, q):
return self.lst[p] == self.lst[q]
def union(self, p, q):
pid = self.lst[p]
qid = self.lst[q]
for ind, x in enumerate(self.lst):
if x == pid:
self.lst[ind] = qid
Cost Model
Both constructor and union class have a for loop that touches the entire array. Connect is the only class that enters the array only once. Union operation touches the entire array every time it does an union of a p with a q. In the worst case, to connect the whole array together, it will touch the entire array N times. That means, it will operate N operations on N element. It takes NxN array access. That why, union operation in quick find is too expensive.
We need to find a better solution. In my next article I will write about the better solution.
