CC-18 : Disjoint set union data structure.

Description:

Disjoint set union data structure has a collection of elements portioned in to disjoint sets. It is forest of disjoint trees with unique elements. The root of the tree is the representative of the tree. Disjoint set union data structure has two operations :

• find(e) : this finds the set in which element belongs, by find its representative using path compression from e to root of its tree.

• union(e, f ) : merges sets containing e, f into same set using representative of e and f and making one representative as parent of another

Implement the Graph Disjoint set union data structure.

Test cases and expected outputs:

Input Parameters	Expected outputs
GraphDisjointSetUnion gph=new GraphDisjointSetUnion(5); gph.union(0,2); gph.union(4,2); gph.union(3,1); boolean isFriend= (gph.find(0)==gph.find(2)); System.out.println("0 is friend of 2: "+isFriend);	0 is friend of 2: true
isFriend= (gph.find(4)==gph.find(1)); System.out.println("4 is friend of 1: "+ isFriend);	4 is friend of 1: false

Pseudocode:

Initialize int array variable parent to hold parent of each vertex. Initially set parent value at each index to index, indicating each vertex is its own parent.

Initialize int array variable rank to hold rank of each vertex. Initially set each rank to 0.

Find() method:

If (vertice==parent[vertice]):

o Return vertice.

Else:

Set parent[vertice] by recursively calling find(parent[vertice]).

Union(vertice 1, vertice2) method:

Set vertice1 to return value from find(vertice1).

Set vertice2 to return value from find(vertice2).

If vertice1 is not equal to vertice2):

If rank[vertice1] is less than rank[vertice2]:

Swap vertice1 and vertice2.

If rank[vertice1] == rank[vertice2]:

Increment rank[vertice1] by 1.

Code:

public class GraphDisjointSetUnion {

private int[] parent;
private int[] rank; 

public GraphDisjointSetUnion(int vertices) {
	parent=new int[vertices];
	rank=new int[vertices];
	
	for (int iIdx=0; iIdx < vertices; iIdx++) {
		parent[iIdx]=iIdx;
		rank[iIdx]=0;
	}
}

public int find(int vertice) {
	if (vertice==parent[vertice]) {
		return vertice;
	}	
	return parent[vertice]=find(parent[vertice]);
}

public void union(int vertice1, int vertice2) {
	vertice1=find(vertice1);
	vertice2=find(vertice2);
	if (vertice1 != vertice2) {
		if (rank[vertice1] < rank[vertice2] ) {
			int tempForSwap=vertice1;
			vertice1=vertice2;
			vertice2=tempForSwap;
		}
		parent[vertice2]=vertice1;
		if (rank[vertice1] == rank[vertice2] ) {
			rank[vertice1]++;
		}
	}
}
}

Click here to download and run code and test cases !

Below fully running code can be copied and run on Eclipse or other Java IDEs. Refer the classname in code below. If the class name below is "A", save the code below to a file named A.java before running it. Be sure to try your own test cases to enhance your understanding ! You can also tweak the code to optimize or add enhancements and custom features.

public class GraphDisjointSetUnion {

private int[] parent;
private int[] rank; 

public GraphDisjointSetUnion(int vertices) {
	parent=new int[vertices];
	rank=new int[vertices];
	
	for (int iIdx=0; iIdx < vertices; iIdx++) {
		parent[iIdx]=iIdx;
		rank[iIdx]=0;
	}
}

public int find(int vertice) {
	if (vertice==parent[vertice]) {
		return vertice;
	}	
	return parent[vertice]=find(parent[vertice]);
}

public void union(int vertice1, int vertice2) {
	vertice1=find(vertice1);
	vertice2=find(vertice2);
	if (vertice1 != vertice2) {
		if (rank[vertice1] < rank[vertice2] ) {
			int tempForSwap=vertice1;
			vertice1=vertice2;
			vertice2=tempForSwap;
		}
		parent[vertice2]=vertice1;
		if (rank[vertice1] == rank[vertice2] ) {
			rank[vertice1]++;
		}
	}
}


public static void main(String[] args) {

	char[][] retVal;
	try {
	GraphDisjointSetUnion gph=new GraphDisjointSetUnion(5);
	gph.union(0,2);
	gph.union(4,2);
	gph.union(3,1);
	boolean isFriend= (gph.find(0)==gph.find(2));
	System.out.println("0 is friend of 2: "+isFriend);
	
	
	isFriend= (gph.find(4)==gph.find(1));
	System.out.println("4 is friend of 1: "+ isFriend);
		
	
	}catch (Exception exception) {
		System.out.print("Exception: "+ exception);
		exception.printStackTrace();
	}
		
}

}