Contents
- How Prim's algorithm works
- Prim's vs Kruskal's
- Implementation
- Complexity Analysis
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 with the smallest edge weight from the priority queue.
- Add u to the MST and record its parent edge.
- For each neighbour v of u, if v is not yet in the MST and the edge weight
is smaller than the current known minimum for v, update and push to the priority queue.
- 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.
| 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) |
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:
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: 8
-
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.
For dense graphs where E ≈ V², Prim's algorithm with a priority queue runs in
O(V² log V), while Kruskal's runs in O(V² log V²) = O(V² log V) — similar performance.
For sparse graphs where E ≈ V, Kruskal's O(V log V) is generally preferred.