[Coursera Algorithms I: Week 1] Quick Find and Quick Union in Java
What is Quick Find
Programming Quick Find in Java
What is Quick Union
Programming Quick Union in Java
Let me give a big shout out to Coursera’s Algorithm I course currently running right now. I went through week 1 lecture material that covered, topics in union find and analyzing algorithm. In this blog post, I will focus on the first part, union find.
Say there are N nodes in a given set. What kind of data
structure would it take to represent that these nodes are
connected to one another? What kind of algorithm would we need
to use to connect one node to another? What do we do to check
if two nodes are connect? These questions will be answered
through learning about quick find and quick union
implementations of union find.
Quick find is an algorithm that places emphasis on finding out
if two nodes are connected or not. We can use a typical array to
represent a set of nodes and their connections to each other.
Indexes of the array are the nodes and the values of the array
are the connections. When the value of one index equals that of
another node’s value, then the two nodes are connected.
Quick Find approach has a very fast method to check connectivity.
To check the connectivity, you just need to access the array
twice. However, union is extremely slow. Since whenever you do
union, you have to go through all the array, you will end up
with O(N) runtime.
The quick find has 3 methods. They are:
constructor: prepares the set as an array
connected: checks if two nodes are connected or not
union: connects two nodes
###To run this java program
Compile the program. javac QuickFind.java
Run the compiled program. java QuickFind
Quick union improves greatly in union operation. Instead of
going through entire array during union, you attach one node’s
root to another’s root.
Edited on Feb 11, 2014
Code for QuickUnion.java and QuickFind.java were updated to fix some