The "eager" algorithm for solving the Dynamic Connectivity problem.

0-quick-find.md

These are part of my notes for the Coursera course: Algorithms, Pt I (Princeton). A setup of the the Dynamic Connectivity problem is explained here

##QuickFind

We make all connected points have the same id-array entries.

A more formal way of putting it is: points are only connected together if their entries in the id-array are the same.
This means that trees have a maximum depth of 2.

For example:

point array   [1] [2] [3] [4] [5] [6] [7]
id array        [2] [2] [3] [2] [3] [6] [2]

  2       3      6
  /|\      |
1 7 3   5

if we connect 2 to 3:

point array   [1] [2] [3] [4] [5] [6] [7]
id array        [3] [3] [3] [3] [3] [6] [3]

      3          6
 ___|___
|   |  |  |   |
1 2 4 5  7

####Running Time #####Check Connected All connected points have the same id-array entries.
It is quick to check if two points are connected - we just compare id-array entries and check to see if they are equal.

#####Union

• All id-array entries in one of the trees will have to be changed to match the root of the other tree.

• This is problematic if we have very large trees (in the billions of entries) that have to be changed every time a new connection is made.

• In the worst case scenario, if we start with unconnected points and then connect all points together.

    change first entry
           |
          1 + 2 + 3 + ... + (N-1) + N
                 |
          add first two points to a third point (etc.)
      = 1/2 * N * (N+1)
      ~ 1/2 * N^2
  

Which is quadratic time.

#####Verdict
The algorithm does not "scale".
It becomes much too slow to be practical at large values of N.

TLDR

• Check-connected: check if id-array entries are equal
• Connect p & q: make all entries with id of p the same as the id of q.
• Time: Quadratic. Too slow to be useful for large N.

QuickFindUF.java

public class QuickFindUF {
	private int[] id;

	public QuickFindUF (int N) 
	{
		id = new int[N];
		for (int i = 0; i < N; i++)
			id[i] = i;
	}

	public 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;
	}

	public void printID()
	{
		StdOut.print("ID array ");
		for (int i = 0; i < id.length; i++)
			StdOut.print("[" + id[i] + "] ");
		StdOut.println("");
	}
}