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:
How this algorithm works?
We strongly recommend reading Find Cycle in Undirected Graph using Disjoint Set (Union-Find) before continue.
- Sort the edges in ascending order of weights.
- 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.
- Repeat the step 2 till spanning tree has V-1 (V – no of vertices in Graph).
- 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.
JavaCode:
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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(); | |
} | |
} |
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