Prim's Algorithm
Last updated
Prim's algorithm builds a minimum spanning tree (MST) - the cheapest set of edges connecting every node with no cycles - by growing a single tree outward from a starting node. At each step it looks at every edge crossing from the tree to a node outside it, and adds the cheapest one. Press play above to watch the tree expand, always taking the lowest-weight edge that reaches a new node.
Because it always picks the minimum crossing edge, each addition is safe (guaranteed to be part of some MST). With a binary-heap priority queue keyed by the cheapest edge to each outside node, Prim runs in O(E log V). It contrasts with Kruskal, which sorts all edges globally instead of growing one connected tree.
Time & space complexity
| Implementation | Complexity | Notes |
|---|---|---|
| Binary heap | O(E log V) | Priority queue of crossing edges |
| Adjacency matrix | O(V²) | Simpler; good for dense graphs |
| Space | O(V + E) | Tree membership + priority queue |
| Best for | Dense graphs | Grows from a single start node |
Step by step
| Step | What happens |
|---|---|
| 1 | Start the tree with any single node. |
| 2 | Look at all edges crossing from the tree to a node outside it. |
| 3 | Pick the crossing edge with the smallest weight. |
| 4 | Add that edge and its new node to the tree. |
| 5 | Repeat until every node is in the tree. |
Worked example
Building the MST of a 4-node graph with edges A-B=1, A-C=3, B-C=2, B-D=4, C-D=5, starting from A:
| Step | Tree | Crossing edges | Chosen edge |
|---|---|---|---|
| 1 | {A} | A-B=1, A-C=3 | A-B (weight 1) |
| 2 | {A, B} | A-C=3, B-C=2, B-D=4 | B-C (weight 2) |
| 3 | {A, B, C} | B-D=4, C-D=5 | B-D (weight 4) |
| 4 | {A, B, C, D} | none - all nodes in tree | done: MST weight 1+2+4 = 7 |
When to use Prim's algorithm
| Use it when | Avoid it when |
|---|---|
| You need a minimum spanning tree of a connected, undirected weighted graph. | The graph is directed or you need shortest paths - use Dijkstra or Bellman-Ford instead. |
The graph is dense (E close to V²); the O(V²) matrix form is simple and fast. | The graph is sparse and edges are already sorted or easy to sort - Kruskal is often simpler. |
| You want the tree to grow from one region outward (e.g. incremental network layout). | The graph is disconnected - Prim only spans one component; you need a minimum spanning forest. |
| You already have an adjacency structure and a priority queue available. | You need to detect cycles across a global edge set - union-find (Kruskal) fits that shape better. |
Prim's Algorithm code
A clean, runnable Prim's Algorithm implementation in Python, JavaScript, Java, C++, C. Pick a language, copy the code, or open it pre-loaded in the Coddy Playground.
Prim's Algorithm code in Python
Python
1import heapq2
3
4def prim(graph, start):5 visited = {start}6 heap = [(w, start, v) for v, w in graph[start]]7 heapq.heapify(heap)8 mst, total = [], 09 while heap and len(visited) < len(graph):10 w, u, v = heapq.heappop(heap)11 if v in visited:12 continue13 visited.add(v)14 mst.append((u, v, w))15 total += w16 # Offer the new node's edges to the frontier17 for neighbor, weight in graph[v]:18 if neighbor not in visited:19 heapq.heappush(heap, (weight, v, neighbor))20 return mst, total21
22
23graph = {24 "A": [("B", 4), ("C", 1)],25 "B": [("A", 4), ("C", 3), ("D", 2)],26 "C": [("A", 1), ("B", 3), ("D", 5)],27 "D": [("B", 2), ("C", 5), ("E", 7)],28 "E": [("D", 7)],29}30
31mst, total = prim(graph, "A")32for u, v, w in mst:33 print(f"{u} - {v} (weight {w})")34print("Total MST weight:", total)Prim's Algorithm code in JavaScript
JavaScript
1const graph = {2 A: { B: 4, C: 2 },3 B: { A: 4, C: 1, D: 5 },4 C: { A: 2, B: 1, D: 8, E: 10 },5 D: { B: 5, C: 8, E: 2 },6 E: { C: 10, D: 2 },7};8
9function prim(start) {10 const inTree = new Set([start]);11 const mst = [];12 let total = 0;13 while (inTree.size < Object.keys(graph).length) {14 // JS has no built-in heap: scan all crossing edges for the cheapest15 let best = null;16 for (const u of inTree) {17 for (const [v, w] of Object.entries(graph[u])) {18 if (!inTree.has(v) && (best === null || w < best[2])) {19 best = [u, v, w];20 }21 }22 }23 const [u, v, w] = best;24 inTree.add(v);25 mst.push(`${u}-${v} (${w})`);26 total += w;27 }28 return { mst, total };29}30
31const { mst, total } = prim("A");32console.log("MST edges:", mst.join(", "));33console.log("Total weight:", total);Prim's Algorithm code in Java
Java
1import java.util.ArrayList;2import java.util.List;3import java.util.PriorityQueue;4
5public class Main {6 public static void main(String[] args) {7 int n = 6;8 List<List<int[]>> adj = new ArrayList<>();9 for (int i = 0; i < n; i++) adj.add(new ArrayList<>());10 int[][] edges = {11 {0, 1, 4}, {0, 2, 3}, {1, 2, 1}, {1, 3, 2},12 {2, 3, 4}, {3, 4, 2}, {4, 5, 6}, {2, 5, 7}13 };14 for (int[] e : edges) {15 adj.get(e[0]).add(new int[]{e[1], e[2]});16 adj.get(e[1]).add(new int[]{e[0], e[2]});17 }18
19 boolean[] inMst = new boolean[n];20 // Always grow the tree along the cheapest crossing edge21 PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[1] - b[1]);22 pq.add(new int[]{0, 0}); // {node, edge weight}23 int total = 0, taken = 0;24 while (!pq.isEmpty() && taken < n) {25 int[] cur = pq.poll();26 if (inMst[cur[0]]) continue;27 inMst[cur[0]] = true;28 total += cur[1];29 taken++;30 for (int[] edge : adj.get(cur[0])) {31 if (!inMst[edge[0]]) pq.add(edge);32 }33 }34 System.out.println("MST nodes reached: " + taken);35 System.out.println("MST total weight: " + total);36 }37}Prim's Algorithm code in C++
C++
1#include <iostream>2#include <queue>3#include <vector>4
5int main() {6 // Undirected weighted graph: adj[u] = {(neighbor, weight), ...}7 std::vector<std::vector<std::pair<int, int>>> adj = {8 {{1, 2}, {3, 6}}, // 09 {{0, 2}, {2, 3}, {3, 8}, {4, 5}}, // 110 {{1, 3}, {4, 7}}, // 211 {{0, 6}, {1, 8}}, // 312 {{1, 5}, {2, 7}}, // 413 };14 int n = static_cast<int>(adj.size());15 std::vector<bool> inMST(n, false);16 using State = std::pair<int, int>; // (edge weight, node)17 std::priority_queue<State, std::vector<State>, std::greater<State>> pq;18 pq.push({0, 0});19 int total = 0, picked = 0;20 // Always grow the tree along the cheapest crossing edge21 while (!pq.empty() && picked < n) {22 auto [w, u] = pq.top();23 pq.pop();24 if (inMST[u]) continue;25 inMST[u] = true;26 total += w;27 ++picked;28 std::cout << "Add node " << u << " (edge weight " << w << ")\n";29 for (auto [v, weight] : adj[u]) {30 if (!inMST[v]) pq.push({weight, v});31 }32 }33 std::cout << "MST total weight: " << total << "\n";34 return 0;35}Prim's Algorithm code in C
C
1#include <stdbool.h>2#include <stdio.h>3
4#define N 55#define INF 10000000006
7int main(void) {8 // Undirected weighted graph: w[u][v] = 0 means no edge9 int w[N][N] = {10 {0, 2, 0, 6, 0},11 {2, 0, 3, 8, 5},12 {0, 3, 0, 0, 7},13 {6, 8, 0, 0, 0},14 {0, 5, 7, 0, 0},15 };16 int key[N], parent[N];17 bool inMST[N] = {false};18 for (int v = 0; v < N; v++) {19 key[v] = INF;20 parent[v] = -1;21 }22 key[0] = 0;23 int total = 0;24 // O(V^2) scan for the cheapest crossing edge (no heap needed here)25 for (int iter = 0; iter < N; iter++) {26 int u = -1;27 for (int v = 0; v < N; v++) {28 if (!inMST[v] && (u == -1 || key[v] < key[u])) u = v;29 }30 inMST[u] = true;31 total += key[u];32 if (parent[u] != -1) {33 printf("Add edge %d - %d (weight %d)\n", parent[u], u, key[u]);34 }35 for (int v = 0; v < N; v++) {36 if (w[u][v] > 0 && !inMST[v] && w[u][v] < key[v]) {37 key[v] = w[u][v];38 parent[v] = u;39 }40 }41 }42 printf("MST total weight: %d\n", total);43 return 0;44}Prim's Algorithm FAQ
What is the time complexity of Prim's algorithm?
With a binary-heap priority queue, Prim runs in
O(E log V). A simpler adjacency-matrix version that scans for the minimum crossing edge each step is O(V²), which can be faster on dense graphs. Both use O(V + E) space.What is the difference between Prim's and Kruskal's algorithm?
Both find a minimum spanning tree greedily. Prim grows one connected tree from a start node, repeatedly adding the cheapest edge that leaves the tree (using a priority queue). Kruskal considers all edges sorted by weight and adds the cheapest that doesn't form a cycle (using union-find). Prim is often preferred on dense graphs, Kruskal on sparse ones.
Does Prim's algorithm always find the optimal MST?
Yes. At every step the cheapest edge crossing the current tree is safe to add - it belongs to some minimum spanning tree (the cut property). Repeatedly adding safe edges yields a genuine minimum spanning tree, provided the graph is connected.
When should I use Prim's algorithm instead of Kruskal's?
Reach for Prim when the graph is dense, because its
O(V²) adjacency-matrix form avoids sorting all E edges and grows one tree from a start node. Kruskal shines on sparse graphs where sorting the edge list is cheap and union-find keeps cycle checks fast. Both produce a correct MST, so the choice is mainly about edge density and which data structures you already have.Does the starting node affect the resulting MST?
No - the total weight of the MST is the same no matter which node you start from, because a connected graph's minimum spanning tree weight is unique. The specific edges can differ only when several edges share the same weight and multiple MSTs exist. Otherwise Prim reaches the exact same tree regardless of start node.
Can Prim's algorithm handle disconnected graphs?
Not directly. Prim grows a single tree, so it only spans the connected component containing the start node and leaves the rest untouched. To cover every component you would run Prim from an unvisited node repeatedly, producing a minimum spanning forest rather than one tree.
Related resources
More visualizations
