Kruskals Algorithm

Kruskals algorithm is used for calculating minimum spanning tree.

Minimum spanning tree is a spanning tree of a connected, undirected graph. It connects all the vertices together with the minimal total weighting for its edges.

minimum spanning tree

minimum spanning tree

Approach for calculating the minimum spanning tree is described as below:

1. Sort all edges by their distance in non decreasing order.
2. Initialize an array which will be holding the parent information for each node. Here we will be using the union-find-algo.
3. For each edge
find root of source and destination i.e. parent
check whether they belongs to the same parent.
if yes, then discard
else keep this edge in the result array of edges
union the source and destination.

import java.util.Arrays;

public class KruskalsAlgo {

	int V;
	Edge[] edges;
	int E;

	public KruskalsAlgo(int v, int e) {
		V = v;
		E = e;
		edges = new Edge[E];
		for(int i = 0; i < E; i++)
			edges[i] = new Edge();
	}

	class Edge implements Comparable<Edge>{

		int src, dest, weight;

		@Override
		public int compareTo(Edge o) {
			int result = 0;
			if(this.weight > o.weight)
				result = 1;
			else if(this.weight < o.weight)
				result = -1;
			return result;
		}
	}
	
	class Subset{
		int parent, rank;

		public Subset(int parent, int rank) {
			this.parent = parent;
			this.rank = rank;
		}
	}
	
	// implement union and find algo on rank i.e. path compression technique. 
	public int find(Subset[] subsets, int i){	
		// find root and make root as parent of i (path compression)
		if(subsets[i].parent != i)
			subsets[i].parent = find(subsets, subsets[i].parent);
		return subsets[i].parent;
	}
	
	// function for doing union of two sets
	public void union(Subset[] subsets, int x, int y){
		int xRoot = find(subsets, x);
		int yRoot = find(subsets, y);
		
		//attach smaller rank tree under higher rank tree
		if(subsets[xRoot].rank > subsets[yRoot].rank)
			subsets[yRoot].parent = xRoot;
		else if(subsets[xRoot].rank < subsets[yRoot].rank)
			subsets[xRoot].parent = yRoot;
		
		// if rank are same, then make one as root and increment it by one
		else{
			subsets[yRoot].parent = xRoot;
			subsets[xRoot].rank ++;
		}
	}
	
	public void kruskal(){
		// sort all the edges
		Arrays.sort(edges);
		
		//allocate memory for V subsets
		Subset[] subsets = new Subset[V];
		for(int i = 0; i < V; i++){
			subsets[i] = new Subset(i, 0);
		}
		
		//result array for the edges
		Edge[] result = new Edge[E];
		
		int count = 0;
		int index = 0;
		
		while(count < V - 1){
			Edge edge = edges[index ++];
			int xroot = find(subsets, edge.src);
			int yroot = find(subsets, edge.dest);
			
			if(xroot != yroot){
				result[count ++] = edge;
				union(subsets, xroot, yroot);
			}
		}
		
		print(result, count);
	}
	
	public void print(Edge[] array, int count){
		for(int i = 0; i < count; i++)
			System.out.println("Edge source :" + array[i].src + ", edge destination: " + array[i].dest + " and weight :" + array[i].weight);
	}jhgdxgtthytgfrfbb 
	
	public static void main(String[] args) {
		KruskalsAlgo graph = new KruskalsAlgo(4,5);
		
		// add edge 0-1
        graph.edges[0].src = 0;
        graph.edges[0].dest = 1;
        graph.edges[0].weight = 10;
 
        // add edge 0-2
        graph.edges[1].src = 0;
        graph.edges[1].dest = 2;
        graph.edges[1].weight = 6;
 
        // add edge 0-3
        graph.edges[2].src = 0;
        graph.edges[2].dest = 3;
        graph.edges[2].weight = 5;
 
        // add edge 1-3
        graph.edges[3].src = 1;
        graph.edges[3].dest = 3;
        graph.edges[3].weight = 15;
 
        // add edge 2-3
        graph.edges[4].src = 2;
        graph.edges[4].dest = 3;
        graph.edges[4].weight = 4;
        
        graph.kruskal();
	}
}

Leave a Reply