Quick Find Algorithm - Coursera Algorithms

Quick Find is an eager union-find algorithm.

Purpose: To find if two elements are connected and to perform union operation on two elements.

We will consider the elements as simple int array. We initialize array to index elements itself and then change the ids in the array when an union operation is performed.

Array accesses: 2N+1
initialize - N
union(p,q) - N
connected(p,q) - 1

If N unions are performed on N elements, union takes N² array access. Quadratic operations don't scale.

Following is the program:

	package Union;
	public class QuickFind {
	private int[] id;
	public QuickFind(int N) {
	id = new int[N];
	for(int i=0;i<N;i++) {
	id[i]=i;
	}
	}
	public void print() {
	System.out.println("************************");
	int n = id.length;
	for(int i=0;i<n;i++) {
	System.out.println(i+"---------"+id[i]);
	}
	}
	public boolean connected(int p, int q) {
	if(id[p]==id[q])
	return true;
	else
	return false;
	}
	public void union(int p, int q) {
	//get all elements with p's id
	//change ids to q's id
	int n = id.length, pid = id[p], qid = id[q];
	for(int i=0;i<n;i++) {
	if(id[i] == pid) {
	id[i]=qid;
	}
	}
	}
	public static void main(String[] args) {
	QuickFind qf = new QuickFind(10);
	qf.union(4, 3);
	qf.union(3, 8);
	qf.print();
	qf.union(6, 5);
	qf.union(9, 4);
	qf.union(2, 1);
	qf.connected(0, 7);
	qf.connected(8, 9);
	qf.union(5, 0);
	qf.union(7, 2);
	qf.connected(0, 7);
	qf.union(1, 0);
	qf.union(6, 1);
	qf.print();
	}
	}

view raw QuickFind.java hosted with ❤ by GitHub