CC-19 : Kruskals algorithm for Minimum Spanning Tree(MST).

Description:

Minimum spanning tree connects all vertices of the undirected graph tree together with minimum weight. The minimum spanning path should not contain any cycles. Kruskals algorithm is one way to find minimum spanning tree. It adds the lowest weight edges that don’t form a cycle first and then connects edges with higher weights till all vertices are connected. Implement the Kruskals MST algorithm for given input graph .

Test cases and expected outputs:

Input Parameters	Expected outputs
GraphKruskalMST gph= new GraphKruskalMST(); edge[] edges=new edge[6]; for (int iIdx=0; iIdx < edges.length; iIdx++) { edges[iIdx]=new edge(); } edges[0].vertice1=0; edges[0].vertice2=1; edges[0].weight=2; edges[1].vertice1=0; edges[1].vertice2=3; edges[1].weight=6; edges[2].vertice1=1; edges[2].vertice2=3; edges[2].weight=8; edges[3].vertice1=1; edges[3].vertice2=2; edges[3].weight=3; edges[4].vertice1=1; edges[4].vertice2=4; edges[4].weight=5; edges[5].vertice1=2; edges[5].vertice2=4; edges[5].weight=7; retVal=gph.kruskalMST(5, edges); System.out.print("Kruskal's MST cost: "+ retVal);	Kruskal's MST cost: 16

Input Parameters

Expected outputs

GraphKruskalMST gph=
new GraphKruskalMST();
edge[] edges=new edge[6];
for (int iIdx=0; iIdx < edges.length; iIdx++) {
edges[iIdx]=new edge();
}
edges[0].vertice1=0; edges[0].vertice2=1; edges[0].weight=2;
edges[1].vertice1=0; edges[1].vertice2=3; edges[1].weight=6;
edges[2].vertice1=1; edges[2].vertice2=3; edges[2].weight=8;
edges[3].vertice1=1; edges[3].vertice2=2; edges[3].weight=3;
edges[4].vertice1=1; edges[4].vertice2=4; edges[4].weight=5;
edges[5].vertice1=2; edges[5].vertice2=4; edges[5].weight=7;
retVal=gph.kruskalMST(5, edges);
System.out.print("Kruskal's MST cost: "+ retVal);

Kruskal's MST cost: 16

Pseudocode:

Edge class:

It contains vertice1, vertice2 and weight of edge as its member variables.

EdgeComparator class:

Implements Comparator interface’s compareTo()method.

Helps to sort edges by the edge’s weight member variable.

GraphDisjointSetUnion class:

Implemented in previous code challenge.

Helps to divide all vertices into 2 sets.

KruskalsMST() method:

Takes vertices count and int array of edges as input parameters.

Use Arrays.sort() method to sort all edges by weight with the help of EdgeComparator class.

Initialize a Disjoint Set Union data structure variable named djsu.

Set int variable named mstCost to 0.

Set int variable named mstCount to 0.

Iterate through edges array using a for loop with iIdx as loop variable and iterate with value of iIdx from 0 to count of edges:

If djsu.find() operation for vertice1 as parameter does not return same value as return value from call to djsu.find() for vertice2 as parameter:

Call djsu.union() with edge[iIdx].vertice1 and edge[iIdx].vertice2 as parameters.

Increment mstcost with edge[iIdx].weight.

If (mstCost==vertices-1), exit the current loop.

Return mstCost.

Code:

public int kruskalMST(int vertices, edge edge[]) {
	Arrays.sort(edge, new edgeComparator());
	GraphDisjointSetUnion djsu=new GraphDisjointSetUnion(vertices);
	int mstCost=0;
	int mstCount=0;
	for (int iIdx=0; iIdx < edge.length; iIdx++) {
		if (djsu.find(edge[iIdx].vertice1) != djsu.find(edge[iIdx].vertice2)){
			djsu.union(edge[iIdx].vertice1, edge[iIdx].vertice2);
			mstCost+=edge[iIdx].weight;
			if (mstCount== vertices-1) {break;}
		}
	}
	return mstCost;
}

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.

import java.util.Arrays;
import java.util.Comparator;

public class GraphKruskalMST {
	
public int kruskalMST(int vertices, edge edge[]) {
	Arrays.sort(edge, new edgeComparator());
	GraphDisjointSetUnion djsu=new GraphDisjointSetUnion(vertices);
	int mstCost=0;
	int mstCount=0;
	for (int iIdx=0; iIdx < edge.length; iIdx++) {
		if (djsu.find(edge[iIdx].vertice1) != djsu.find(edge[iIdx].vertice2)){
			djsu.union(edge[iIdx].vertice1, edge[iIdx].vertice2);
			mstCost+=edge[iIdx].weight;
			if (mstCount== vertices-1) {break;}
		}
	}
	return mstCost;
}

public static void main(String[] args) {
	/***********************
	 Test cases given below:
	 **********************/
	int retVal;
	try {
	GraphKruskalMST gph=new GraphKruskalMST();
	edge[] edges=new edge[6];
	for (int iIdx=0; iIdx < edges.length; iIdx++) {
		edges[iIdx]=new edge();		
	}	
	edges[0].vertice1=0; edges[0].vertice2=1; edges[0].weight=2; 
	edges[1].vertice1=0; edges[1].vertice2=3; edges[1].weight=6; 
	edges[2].vertice1=1; edges[2].vertice2=3; edges[2].weight=8; 
	edges[3].vertice1=1; edges[3].vertice2=2; edges[3].weight=3; 
	edges[4].vertice1=1; edges[4].vertice2=4; edges[4].weight=5; 
	edges[5].vertice1=2; edges[5].vertice2=4; edges[5].weight=7; 
	retVal=gph.kruskalMST(5, edges);
	System.out.print("Kruskal's MST cost: "+ retVal);
	
}catch (Exception exception) {
		System.out.print("Exception: "+ exception);
		exception.printStackTrace();
	}
		
}

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]++;
		}
	}
}
}


}

class edge{
	public int vertice1;
	public int vertice2;
	public int weight;
}

class edgeComparator implements Comparator<edge>{
	public int compare(edge edge1, edge edge2) {
		if (edge1.weight < edge2.weight) {
			return-1;
		}
		if (edge1.weight > edge2.weight) {
			return 1;
		}
		return 0;
	}
}