Kruskal’s Algorithm – Minimum Spanning Tree (MST) – Complete Java Implementation

by

What is Kruskal Algorithm?

  • Kruskal’s algorithm for finding the Minimum Spanning Tree(MST), which finds an edge of the least possible weight that connects any two trees in the forest
  • It is a greedy algorithm.
  • It finds a subset of the edges that forms a tree that includes every vertex, where the total weight of all the edges in the tree is minimized.
  • If the graph is not connected, then it finds a minimum spanning forest (a minimum spanning tree for each connected component).
  • Number of edges in MST: V-1 (V – no of vertices in Graph).

Example:

Minimum Spanning Tree (MST) Example

How this algorithm works?

We strongly recommend reading Find Cycle in Undirected Graph using Disjoint Set (Union-Find) before continue.

  1. Sort the edges in ascending order of weights.
  2. Pick the edge with the least weight. Check if including this edge in spanning tree will form a cycle is Yes then ignore it if No then add it to spanning tree.
  3. Repeat the step 2 till spanning tree has V-1 (V – no of vertices in Graph).
  4. Spanning tree with least weight will be formed, called Minimum Spanning Tree

Pseudo Code:

KRUSKAL(G):
A = ∅
foreach v ∈ G.V:
   MAKE-SET(v)
foreach (u, v) in G.E ordered by weight(u, v), increasing:
   if FIND-SET(u) ≠ FIND-SET(v):
      A = A ∪ {(u, v)}
      UNION(u, v)
return A

See the animation below for more understanding.

1/9
2/9
Kruskal -3
Kruskal -4
Kruskal -5
Kruskal -6
Kruskal -7
Kruskal -8
Kruskal -9
previous arrow
PlayPause
next arrow

JavaCode:

import java.util.ArrayList;
import java.util.Comparator;
import java.util.PriorityQueue;
public class KrushkalMST {
static class Edge {
int source;
int destination;
int weight;
public Edge(int source, int destination, int weight) {
this.source = source;
this.destination = destination;
this.weight = weight;
}
}
static class Graph {
int vertices;
ArrayList<Edge> allEdges = new ArrayList<>();
Graph(int vertices) {
this.vertices = vertices;
}
public void addEgde(int source, int destination, int weight) {
Edge edge = new Edge(source, destination, weight);
allEdges.add(edge); //add to total edges
}
public void kruskalMST(){
PriorityQueue<Edge> pq = new PriorityQueue<>(allEdges.size(), Comparator.comparingInt(o –> o.weight));
//add all the edges to priority queue, //sort the edges on weights
for (int i = 0; i <allEdges.size() ; i++) {
pq.add(allEdges.get(i));
}
//create a parent []
int [] parent = new int[vertices];
//makeset
makeSet(parent);
ArrayList<Edge> mst = new ArrayList<>();
//process vertices – 1 edges
int index = 0;
while(index<vertices–1){
Edge edge = pq.remove();
//check if adding this edge creates a cycle
int x_set = find(parent, edge.source);
int y_set = find(parent, edge.destination);
if(x_set==y_set){
//ignore, will create cycle
}else {
//add it to our final result
mst.add(edge);
index++;
union(parent,x_set,y_set);
}
}
//print MST
System.out.println("Minimum Spanning Tree: ");
printGraph(mst);
}
public void makeSet(int [] parent){
//Make set- creating a new element with a parent pointer to itself.
for (int i = 0; i <vertices ; i++) {
parent[i] = i;
}
}
public int find(int [] parent, int vertex){
//chain of parent pointers from x upwards through the tree
// until an element is reached whose parent is itself
if(parent[vertex]!=vertex)
return find(parent, parent[vertex]);;
return vertex;
}
public void union(int [] parent, int x, int y){
int x_set_parent = find(parent, x);
int y_set_parent = find(parent, y);
//make x as parent of y
parent[y_set_parent] = x_set_parent;
}
public void printGraph(ArrayList<Edge> edgeList){
for (int i = 0; i <edgeList.size() ; i++) {
Edge edge = edgeList.get(i);
System.out.println("Edge-" + i + " source: " + edge.source +
" destination: " + edge.destination +
" weight: " + edge.weight);
}
}
}
public static void main(String[] args) {
int vertices = 6;
Graph graph = new Graph(vertices);
graph.addEgde(0, 1, 4);
graph.addEgde(0, 2, 3);
graph.addEgde(1, 2, 1);
graph.addEgde(1, 3, 2);
graph.addEgde(2, 3, 4);
graph.addEgde(3, 4, 2);
graph.addEgde(4, 5, 6);
graph.kruskalMST();
}
}

view raw
KrushkalMST.java
hosted with ❤ by GitHub


Output:

Minimum Spanning Tree:
Edge-0 source: 1 destination: 2 weight: 1
Edge-1 source: 1 destination: 3 weight: 2
Edge-2 source: 3 destination: 4 weight: 2
Edge-3 source: 0 destination: 2 weight: 3
Edge-4 source: 4 destination: 5 weight: 6

Click here to read about – Minimum Spanning Tree using Prim’s Algorithm

Reference – Wiki

Related Posts: