Graph - Prim's Minimum Spanning Tree (MST)
Prim's algorithm finds the Minimum Spanning Tree (MST) of a connected, weighted, undirected graph. Unlike Kruskal's which works edge by edge, Prim's grows the MST one vertex at a time: always picking the cheapest edge that connects a new vertex to the already-built MST.
How Prim's algorithm works
Prim's algorithm maintains two sets of vertices:
- In-MST set: vertices already included in the MST.
- Out-MST set: vertices not yet included.
At every step, it picks the minimum weight edge that connects a vertex inside the MST to a vertex outside it, and adds the outside vertex to the MST.
Algorithm steps:
- Start with any arbitrary vertex as the initial MST node.
- Use a Min-Heap (priority queue) to track the minimum-weight edge crossing the cut between In-MST and Out-MST vertices.
- Extract the vertex
u - Add
u - For each neighbour
vuvv - Repeat until all vertices are in the MST.
Prim's algorithm is similar in structure to Dijkstra's algorithm. The key difference is that
Dijkstra minimises the total path distance from the source, while Prim minimises
the weight of the edge added to the MST.
Prim's vs Kruskal's
| Aspect | Prim's | Kruskal's |
|---|---|---|
| Approach | Grows MST vertex by vertex | Grows MST edge by edge |
| Data structure | Min-Heap (Priority Queue) | Sorted edges + Union-Find |
| Best for | Dense graphs (many edges) | Sparse graphs (few edges) |
| Time complexity | O((V + E) log V) | O(E log E) |
Implementation
The class below shows the implementation. Key points are highlighted in the inline comments.
Java
import java.util.*;
public class Prim {
static class Edge {
int dest, weight;
Edge(int dest, int weight) { this.dest = dest; this.weight = weight; }
}
/**
* Finds the MST using Prim's algorithm.
* @param graph adjacency list: graph[u] = list of Edge(v, w)
* @param V number of vertices
* @return total weight of the MST
*/
public int primMST(List<List<Edge>> graph, int V) {
int[] key = new int[V]; // minimum edge weight to include each vertex
boolean[] inMST = new boolean[V]; // whether vertex is in MST
int[] parent = new int[V]; // parent of each vertex in MST
Arrays.fill(key, Integer.MAX_VALUE);
Arrays.fill(parent, -1);
key[0] = 0; // start from vertex 0
// Min-heap: (key/weight, vertex)
PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a[0]));
pq.offer(new int[]{0, 0});
int totalWeight = 0;
while (!pq.isEmpty()) {
int[] curr = pq.poll();
int u = curr[1];
if (inMST[u]) continue; // already processed
inMST[u] = true;
totalWeight += curr[0];
for (Edge edge : graph.get(u)) {
int v = edge.dest, w = edge.weight;
if (!inMST[v] && w < key[v]) {
key[v] = w;
parent[v] = u;
pq.offer(new int[]{w, v});
}
}
}
// Print MST edges
System.out.println("MST edges:");
for (int i = 1; i < V; i++) {
System.out.println(parent[i] + " -- " + i + " : " + key[i]);
}
return totalWeight;
}
}Example usage:
Java
int V = 5;
List<List<Prim.Edge>> graph = new ArrayList<>();
for (int i = 0; i < V; i++) graph.add(new ArrayList<>());
// Add undirected edges (add both directions)
graph.get(0).add(new Prim.Edge(1, 4)); graph.get(1).add(new Prim.Edge(0, 4));
graph.get(0).add(new Prim.Edge(2, 3)); graph.get(2).add(new Prim.Edge(0, 3));
graph.get(1).add(new Prim.Edge(2, 1)); graph.get(2).add(new Prim.Edge(1, 1));
graph.get(1).add(new Prim.Edge(3, 2)); graph.get(3).add(new Prim.Edge(1, 2));
graph.get(2).add(new Prim.Edge(3, 4)); graph.get(3).add(new Prim.Edge(2, 4));
graph.get(3).add(new Prim.Edge(4, 2)); graph.get(4).add(new Prim.Edge(3, 2));
Prim p = new Prim();
int total = p.primMST(graph, V);
System.out.println("Total MST weight: " + total);
// MST edges:
// 2 -- 1 : 1
// 0 -- 2 : 3
// 1 -- 3 : 2
// 3 -- 4 : 2
// Total MST weight: 8Complexity Analysis
- Time complexity: O((V + E) log V). Each vertex is extracted from the priority queue once (O(V log V)) and each edge can be relaxed once (O(E log V)).
- Space complexity: O(V + E). For the key, parent, and inMST arrays plus the priority queue.
Note:
For dense graphs where E ≈ V²E ≈ V