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

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.

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    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 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 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 mst = new ArrayList<>(); //process vertices – 1 edges int index = 0; while(index edgeList){ for (int i = 0; i

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
```