Imagine the government wants to connect five villages with fibre-optic cable.
Engineers have surveyed which pairs of villages can be connected, and how much each cable would cost. The goal:
1. Every village must be connected (directly or through others).
2. The total cost must be as small as possible.There is no reason to lay a cable that creates a loop, because the villages on that loop are already connected. So the cheapest network will always be a tree.
This tree is called a Minimum Spanning Tree, or MST.
A Minimum Spanning Tree of a connected, undirected, weighted graph is a subset of its edges that connects all the vertices, contains no cycle, and has the smallest possible total edge weight.
In this chapter, you will learn the two famous algorithms that find it: Kruskal's algorithm and Prim's algorithm. Both build on things you already know: Disjoint Set Union and Priority Queue.
What Is a Spanning Tree?
Let's break the name into parts.
Spanning: it reaches (spans) every vertex of the graph.
Tree: it is connected and has no cycles.
Take this graph:
A ─── B
│ ╲ │
C ─── D
Edges: A-B, A-C, A-D, B-D, C-DHere are two of its spanning trees:
Spanning tree 1 Spanning tree 2
A ─── B A ─── B
│ │ ╲
C D C ─── D
Edges: A-B, A-C, B-D Edges: A-B, A-D, C-DBoth connect all 4 vertices, and neither has a cycle.
Important facts about spanning trees:
A spanning tree of a graph with
Vvertices always has exactlyV - 1edges.Adding any other edge to it creates exactly one cycle.
Removing any edge from it disconnects it.
A graph usually has many spanning trees. A complete graph with
nvertices hasnⁿ⁻²of them (Cayley's formula), so even 4 fully connected vertices have 16.Only a connected graph has a spanning tree.
What Makes It "Minimum"?
When edges have weights (costs, distances, prices), different spanning trees have different total weights.
The minimum spanning tree is the one with the smallest total.
Here is the graph we will use for the rest of this chapter:
2 3
0 ───── 1 ───── 2
│ / \ │
6 │ / 8 5 \ │ 4
│ / \ │
3 ───────────── 4
9Edge | Weight |
|---|---|
0 - 1 | 2 |
0 - 3 | 6 |
1 - 2 | 3 |
1 - 3 | 8 |
1 - 4 | 5 |
2 - 4 | 4 |
3 - 4 | 9 |
It has 5 vertices, so any spanning tree has 4 edges. The MST (which we will find in a moment) is:
2 3
0 ───── 1 ───── 2
│ │
6 │ │ 4
│ │
3 4
Edges: 0-1 (2), 1-2 (3), 2-4 (4), 0-3 (6)
Total weight = 2 + 3 + 4 + 6 = 15No other spanning tree of this graph has a total weight of 15 or less.
Where Is MST Used?
Network design: laying cables, pipelines, roads or electrical grids at minimum cost.
Clustering: build an MST and remove the most expensive edges to split data into groups.
Approximation algorithms: a quick, good-enough answer for hard problems like the Travelling Salesman Problem.
Image segmentation: grouping similar neighbouring pixels.
Two Key Properties (Why Greedy Works)
Both MST algorithms are greedy: they repeatedly pick the cheapest edge that is safe to add, and never go back. That only works because of two properties. For simplicity, assume all edge weights are different.
The Cut Property
Split the vertices into any two groups. Among all edges that go between the two groups, the cheapest one must be in the MST.
Group X = {0} Group Y = {1, 2, 3, 4}
Edges crossing: 0-1 (2), 0-3 (6)
Cheapest: 0-1 (2) → must be in the MSTWhy? The MST must connect the two groups somehow. If it used a more expensive crossing edge instead, we could swap it for the cheaper one and get a lighter spanning tree. Prim's algorithm is built on this idea.
The Cycle Property
In any cycle, the most expensive edge is never in the MST.
Cycle: 1 - 2 - 4 - 1
Weights: 1-2 (3), 2-4 (4), 1-4 (5)
Most expensive: 1-4 (5) → not in the MSTThe other edges of the cycle already connect its vertices, so the heaviest edge is never needed. Kruskal's algorithm is built on this idea.
Is the MST Unique?
If all edge weights are different, there is exactly one MST.
If some weights are equal, there can be several MSTs, but they all have the same total weight. So if a problem asks for the minimum cost, the answer is always unique, even if the edges chosen are not.
Kruskal's Algorithm
Kruskal's idea is very simple:
Kruskal's algorithm: go through the edges from cheapest to most expensive, and add each edge unless it creates a cycle.
1. Sort all edges by weight.
2. Start with every vertex in its own group.
3. For each edge (u, v) in sorted order:
if u and v are in different groups:
add the edge to the MST
merge the two groups
else:
skip it (it would create a cycle)
4. Stop when the MST has V - 1 edges.How do we check "would this edge create a cycle?" quickly? With Disjoint Set Union from the previous chapter:
find(u) != find(v) → different groups, safe to add, then union(u, v)
find(u) == find(v) → already connected, adding it makes a cycleKruskal's Algorithm Step by Step
Sort the edges:
0-1 (2)
1-2 (3)
2-4 (4)
1-4 (5)
0-3 (6)
1-3 (8)
3-4 (9)Groups at the start:
{0} {1} {2} {3} {4}Edge 0-1 (2)
0 and 1 are in different groups. Take it.
{0, 1} {2} {3} {4} MST weight = 2Edge 1-2 (3)
Different groups. Take it.
{0, 1, 2} {3} {4} MST weight = 5Edge 2-4 (4)
Different groups. Take it.
{0, 1, 2, 4} {3} MST weight = 9Edge 1-4 (5)
1 and 4 are already in the same group (through 1 → 2 → 4). Adding this edge would create the cycle 1 - 2 - 4 - 1. Skip it.
Edge 0-3 (6)
Different groups. Take it.
{0, 1, 2, 3, 4} MST weight = 15Now the MST has 4 = V - 1 edges, so we stop. Edges 1-3 and 3-4 are never even looked at.
Kruskal's Algorithm in Java
We store the graph as an edge list, because Kruskal works with edges directly. The find and union functions are the same as in the DSU chapter.
import java.util.ArrayList;
import java.util.Collections;
class Edge {
int u, v, weight;
Edge(int u, int v, int weight) {
this.u = u;
this.v = v;
this.weight = weight;
}
}
class Main {
static int[] parent;
static int[] size;
static int find(int x) {
if (parent[x] != x) {
parent[x] = find(parent[x]);
}
return parent[x];
}
static boolean union(int a, int b) {
int rootA = find(a);
int rootB = find(b);
if (rootA == rootB) {
return false;
}
if (size[rootA] < size[rootB]) {
int temp = rootA;
rootA = rootB;
rootB = temp;
}
parent[rootB] = rootA;
size[rootA] += size[rootB];
return true;
}
static int kruskal(int vertices, ArrayList<Edge> edges) {
// Step 1: sort edges by weight
Collections.sort(edges, (a, b) -> Integer.compare(a.weight, b.weight));
parent = new int[vertices];
size = new int[vertices];
for (int i = 0; i < vertices; i++) {
parent[i] = i;
size[i] = 1;
}
int totalWeight = 0;
int edgesUsed = 0;
// Step 2: pick edges that do not form a cycle
for (Edge e : edges) {
if (union(e.u, e.v)) {
System.out.println("Take " + e.u + " - " + e.v + " (" + e.weight + ")");
totalWeight += e.weight;
edgesUsed++;
if (edgesUsed == vertices - 1) {
break; // MST is complete
}
} else {
System.out.println("Skip " + e.u + " - " + e.v + " (" + e.weight + ") cycle");
}
}
if (edgesUsed != vertices - 1) {
return -1; // graph is not connected
}
return totalWeight;
}
public static void main(String[] args) {
int vertices = 5;
ArrayList<Edge> edges = new ArrayList<>();
edges.add(new Edge(0, 1, 2));
edges.add(new Edge(0, 3, 6));
edges.add(new Edge(1, 2, 3));
edges.add(new Edge(1, 3, 8));
edges.add(new Edge(1, 4, 5));
edges.add(new Edge(2, 4, 4));
edges.add(new Edge(3, 4, 9));
int total = kruskal(vertices, edges);
System.out.println("Total MST weight: " + total);
}
}Output:
Take 0 - 1 (2)
Take 1 - 2 (3)
Take 2 - 4 (4)
Skip 1 - 4 (5) cycle
Take 0 - 3 (6)
Total MST weight: 15If the graph is not connected, we can never collect V - 1 edges, so the function returns -1.
Kruskal's Complexity
Sorting the edges → O(E log E)
DSU operations → O(E · α(V)) (almost O(E))
Total time → O(E log E)
Space → O(V + E)Since E is at most V², log E is at most 2 log V. So O(E log E) is the same as O(E log V), and you will see both written.
Prim's Algorithm
Prim's algorithm grows the MST like a tree spreading from one starting point.
Prim's algorithm: start from any vertex, and repeatedly add the cheapest edge that connects a vertex inside the tree to a vertex outside it.
This is the cut property in action: "inside the tree" and "outside the tree" are the two groups, and we always take the cheapest edge crossing between them.
To find that cheapest edge quickly, we use a min priority queue, just as hinted in the Priority Queue chapter.
1. Put (weight 0, start vertex) into a min priority queue.
2. While the queue is not empty:
remove the entry with the smallest weight → (w, v)
if v is already in the tree: skip it
add v to the tree, add w to the total
for every edge v - u with weight x:
if u is not in the tree:
add (x, u) to the queueThe queue may contain extra, out-of-date entries for a vertex that has already joined the tree through a cheaper edge. We simply skip them when they come out. This is called the lazy version of Prim's algorithm, and it is the one most people write in interviews.
Prim's Algorithm Step by Step
We start from vertex 0. Queue entries are written as (weight, vertex).
Step 1: Take vertex 0
Tree = {0}
Queue = (2, 1), (6, 3)Step 2: Cheapest is (2, 1)
Add edge 0 - 1. Push the edges of 1 that lead outside the tree.
Tree = {0, 1} total = 2
Queue = (3, 2), (5, 4), (6, 3), (8, 3)Step 3: Cheapest is (3, 2)
Add edge 1 - 2.
Tree = {0, 1, 2} total = 5
Queue = (4, 4), (5, 4), (6, 3), (8, 3)Step 4: Cheapest is (4, 4)
Add edge 2 - 4.
Tree = {0, 1, 2, 4} total = 9
Queue = (5, 4), (6, 3), (8, 3), (9, 3)Step 5: Cheapest is (5, 4)
Vertex 4 is already in the tree. This is a stale entry. Skip it.
Step 6: Cheapest is (6, 3)
Add edge 0 - 3.
Tree = {0, 1, 2, 3, 4} total = 15All 5 vertices are in the tree. Prim's algorithm finds the same MST as Kruskal's, with total weight 15.
Prim's Algorithm in Java
Prim works naturally with an adjacency list. Each list entry is {neighbor, weight}, and each queue entry is {weight, node, parent}. We keep the parent only so we can print which edge was added.
import java.util.ArrayList;
import java.util.PriorityQueue;
class Main {
static void addEdge(
ArrayList<ArrayList<int[]>> graph,
int u,
int v,
int weight
) {
// each entry is {neighbor, weight}
graph.get(u).add(new int[] {v, weight});
graph.get(v).add(new int[] {u, weight});
}
static int prim(ArrayList<ArrayList<int[]>> graph) {
int vertices = graph.size();
boolean[] inMST = new boolean[vertices];
// each entry is {weight, node, parent}, smallest weight first
PriorityQueue<int[]> pq =
new PriorityQueue<>((a, b) -> Integer.compare(a[0], b[0]));
pq.add(new int[] {0, 0, -1}); // start from vertex 0
int totalWeight = 0;
int added = 0;
while (!pq.isEmpty() && added < vertices) {
int[] top = pq.poll();
int weight = top[0];
int node = top[1];
int parent = top[2];
if (inMST[node]) {
continue; // stale entry, node already in the tree
}
inMST[node] = true;
totalWeight += weight;
added++;
if (parent != -1) {
System.out.println("Add " + parent + " - " + node + " (" + weight + ")");
}
for (int[] edge : graph.get(node)) {
int next = edge[0];
int w = edge[1];
if (!inMST[next]) {
pq.add(new int[] {w, next, node});
}
}
}
if (added != vertices) {
return -1; // graph is not connected
}
return totalWeight;
}
public static void main(String[] args) {
int vertices = 5;
ArrayList<ArrayList<int[]>> graph = new ArrayList<>();
for (int i = 0; i < vertices; i++) {
graph.add(new ArrayList<>());
}
addEdge(graph, 0, 1, 2);
addEdge(graph, 0, 3, 6);
addEdge(graph, 1, 2, 3);
addEdge(graph, 1, 3, 8);
addEdge(graph, 1, 4, 5);
addEdge(graph, 2, 4, 4);
addEdge(graph, 3, 4, 9);
System.out.println("Total MST weight: " + prim(graph));
}
}Output:
Add 0 - 1 (2)
Add 1 - 2 (3)
Add 2 - 4 (4)
Add 0 - 3 (6)
Total MST weight: 15We compare with Integer.compare(a[0], b[0]) instead of a[0] - b[0], because subtraction can overflow when weights are very large or negative.
Prim's Complexity
Every edge can push one entry into the priority queue, and each push or pop costs O(log E).
Time → O(E log E) = O(E log V)
Space → O(V + E)Prim's Algorithm for Dense Graphs: O(V²)
When the graph is dense (almost every pair of vertices has an edge), E is close to V², and building an edge list or priority queue becomes expensive.
In that case, Prim's algorithm can skip the priority queue completely. Keep an array minDist[], the cheapest known edge from the tree to each outside vertex, and pick the minimum with a simple loop.
A classic example is Min Cost to Connect All Points (LeetCode 1584): given points on a 2D plane, connect them all with minimum total cost, where the cost between two points is their Manhattan distance |x1 - x2| + |y1 - y2|. Every pair of points can be connected, so the graph is complete.
import java.util.Arrays;
class Main {
// Prim's algorithm without a heap: O(n^2), ideal for dense graphs
static int minCostConnectPoints(int[][] points) {
int n = points.length;
boolean[] inMST = new boolean[n];
int[] minDist = new int[n]; // cheapest edge from the tree to each point
Arrays.fill(minDist, Integer.MAX_VALUE);
minDist[0] = 0;
int total = 0;
for (int step = 0; step < n; step++) {
// pick the closest point not yet in the tree
int u = -1;
for (int i = 0; i < n; i++) {
if (!inMST[i] && (u == -1 || minDist[i] < minDist[u])) {
u = i;
}
}
inMST[u] = true;
total += minDist[u];
// update distances using the newly added point
for (int v = 0; v < n; v++) {
if (!inMST[v]) {
int dist = Math.abs(points[u][0] - points[v][0])
+ Math.abs(points[u][1] - points[v][1]);
minDist[v] = Math.min(minDist[v], dist);
}
}
}
return total;
}
public static void main(String[] args) {
int[][] points = {{0, 0}, {2, 2}, {3, 10}, {5, 2}, {7, 0}};
System.out.println("Minimum cost: " + minCostConnectPoints(points));
}
}Output:
Minimum cost: 20There are n steps, and each step scans all n points twice, so the time is O(n²) and the extra space is O(n). Kruskal's algorithm would need to build and sort all n(n - 1) / 2 edges, which costs O(n² log n) time and O(n²) memory.
Kruskal vs Prim
Kruskal | Prim | |
|---|---|---|
Idea | Pick the cheapest edges globally, skip cycles | Grow one tree from a start vertex |
Main tool | Sorting + DSU | Priority queue (or a simple array) |
Graph format | Edge list | Adjacency list (or matrix) |
Time |
|
|
Best for | Sparse graphs, edges given as a list | Dense graphs |
Disconnected graph | Naturally builds a minimum spanning forest | Only covers the start vertex's component |
Both always give an MST with the same total weight. In interviews, pick the one you can write correctly fastest. Kruskal is often shorter if you already have a DSU template.
MST Is Not the Shortest Path
This is a very common confusion.
The MST minimizes the total weight of the whole network. It does not guarantee the shortest route between two particular vertices.
A
2 / \ 3
/ \
B ─── C
2The MST is A-B (2) and B-C (2), with total weight 4. The edge A-C (3) is the heaviest in the only cycle, so it is left out.
But the shortest path from A to C is the direct edge, with length 3. Inside the MST, going from A to C costs 2 + 2 = 4.
Minimum Spanning Tree | Shortest Path |
|---|---|
Connect all vertices as cheaply as possible | Go from one vertex to another as cheaply as possible |
Kruskal, Prim | BFS (unweighted), Dijkstra (next chapter) |
Undirected graphs | Directed or undirected |
Special Cases
Disconnected Graph
A disconnected graph has no spanning tree. Kruskal's algorithm will still connect each component as cheaply as possible, giving a minimum spanning forest. Our code returns -1 to signal that a single tree is impossible.
Negative Weights
MST algorithms work perfectly with negative weights. They only compare weights against each other, so negative values cause no problems.
Maximum Spanning Tree
Need the most expensive spanning tree instead? Sort the edges in descending order in Kruskal's algorithm (or use a max priority queue in Prim's). Everything else stays the same.
Directed Graphs
Kruskal and Prim are for undirected graphs only. The directed version of the problem (called a minimum spanning arborescence) needs a different, more advanced algorithm and rarely appears in placement interviews.
Common Mistakes
1. Forgetting to check for a cycle in Kruskal
Simply taking the V - 1 cheapest edges does not work. In our graph, the 4 cheapest edges are 0-1, 1-2, 2-4, 1-4, which form a cycle and leave vertex 3 disconnected.
2. Not skipping stale entries in Prim
Without the if (inMST[node]) continue; check, a vertex can be added twice and its weight counted twice.
3. Adding undirected edges only once in Prim
Prim's adjacency list must store each edge in both directions. Kruskal's edge list stores each edge only once.
4. Integer overflow
With many large weights, the total can exceed the int range. Use long for the total when weights can be large.
5. Assuming the graph is connected
Always check that the MST has V - 1 edges (Kruskal) or V vertices (Prim) before returning the answer.
6. Confusing MST with shortest path
If the question asks for the cheapest route between two places, you need a shortest path algorithm, not an MST.
Practice Problems
Minimum Spanning Tree (GeeksforGeeks), return the MST weight
Min Cost to Connect All Points (LeetCode 1584)
Connecting Cities With Minimum Cost (LeetCode 1135)
Optimize Water Distribution in a Village (LeetCode 1168), add a virtual vertex for wells
Find Critical and Pseudo-Critical Edges in MST (LeetCode 1489), a harder Kruskal problem
Interview Tips
Keywords like connect all, minimum cost to connect, cheapest network or lay cables/roads usually mean MST.
Be ready to explain why greedy works, using the cut property or the cycle property.
Know both algorithms, their complexities, and when each is better (Kruskal for sparse graphs with an edge list, Prim for dense graphs).
Mention that an MST has exactly
V - 1edges, and that it exists only for connected graphs.
The Main Idea
A Minimum Spanning Tree connects every vertex of a weighted, undirected, connected graph using V - 1 edges with the smallest possible total weight.
Two greedy algorithms find it:
Kruskal
sort edges by weight
take an edge if it doesn't form a cycle (checked with DSU)
Time → O(E log E)
Prim
grow a tree from one vertex
always add the cheapest edge leaving the tree (min priority queue)
Time → O(E log V), or O(V²) for dense graphsBoth rely on two facts:
Cut property → the cheapest edge across any cut belongs to the MST
Cycle property → the most expensive edge in any cycle does notKruskal thinks about edges, Prim thinks about vertices, and both arrive at the same minimum total cost.
In the next chapter, we will solve a different problem on weighted graphs, finding the shortest path from one vertex to all others, using Dijkstra's Algorithm.