Prim's algorithm
mediumGrow a single tree by absorbing the cheapest edge leaving it. The only difference from Dijkstra is the priority: distance from the tree, not distance from the source.
O(E log V)Space O(V)Saved in this browser - no sign-up, nothing sent anywhere.
How prim's algorithm works
Prim grows one tree from a seed vertex, and at every step absorbs the cheapest edge leaving the tree. The tree and everything outside it form a cut; by the cut property the lightest crossing edge is safe, so each absorption is provably part of some minimum spanning tree.
The machinery is Dijkstra's with one line changed. Both pop the minimum from a priority queue, both push candidates lazily, both discard stale entries on pop. Dijkstra's key is dist[u] + w, total distance from the source; Prim's is just w, the edge's own weight - distance from the tree.
Kruskal reaches the same total from the opposite direction: it sorts all edges globally and grows many fragments that merge, where Prim grows a single blob outward. On the default graph both arrive at weight 19. Prim suits dense graphs and adjacency structures - there is no sort, only heap operations.
Step by step
- Seed the tree with A and queue its edges: A-B at 4, A-D at 2. The cheapest edge leaving the tree is always safe.
- Pop A-D at 2 and absorb D. D's outward edges enter the queue: D-E at 5, D-G at 7.
- Pop A-B at 4, absorbing B - cheaper than everything D offered. B contributes B-E at 3 and B-C at 6.
- B-E at 3 wins next, then E-H at 3. Each absorbed vertex refreshes the frontier with its own edges.
- H's edge H-G costs just 1 - it jumps the queue and G is absorbed. The candidate D-G at 7 is now pointless and gets dropped.
- E-F at 4 and F-C at 2 finish the job: 8 vertices, 7 edges, total weight 19 - the same total Kruskal finds.
Complexity
| Worst case time | O(E log V) |
|---|---|
| Space | O(V) |
Same cut property as Kruskal, applied to a different cut each round.
Reference implementation
Python
import heapq
def prim(adj, start):
in_tree = {start}
pq = [(w, start, v) for v, w in adj[start]]
heapq.heapify(pq)
mst, total = [], 0
while pq and len(in_tree) < len(adj):
w, u, v = heapq.heappop(pq)
if v in in_tree:
continue # stale entry
in_tree.add(v)
mst.append((u, v, w))
total += w
for x, w2 in adj[v]:
if x not in in_tree:
heapq.heappush(pq, (w2, v, x))
return mst, totalJavaScript
function prim(adj, start) {
const inTree = new Set([start]);
const pq = (adj.get(start) ?? []).map(({ to, w }) => [w, start, to]);
const mst = [];
let total = 0;
while (pq.length && inTree.size < adj.size) {
pq.sort((a, b) => a[0] - b[0]);
const [w, u, v] = pq.shift();
if (inTree.has(v)) continue;
inTree.add(v);
mst.push([u, v, w]);
total += w;
for (const { to: x, w: w2 } of adj.get(v) ?? []) {
if (!inTree.has(x)) pq.push([w2, v, x]);
}
}
return { mst, total };
}Worth noticing
One growing tree, not a forest
Prim keeps a single connected blob and repeatedly absorbs the cheapest edge leaving it. Kruskal, by contrast, builds disconnected fragments that eventually merge. Both end at the same total weight.
Dijkstra with one line changed
Dijkstra's priority is dist[u] + w - distance from the source. Prim's is just w - distance from the tree. Everything else, including the stale-entry handling, is identical.
The cut property again
At every step the tree and its complement form a cut, and the cheapest edge crossing it is safe to take. That is the same theorem that justifies Kruskal, applied to a different cut each round.
Common pitfalls
- Skipping the in-tree check on pop. The queue accumulates multiple entries per vertex; absorbing one already inside the tree adds a cycle and double-counts weight.
- Copying Dijkstra too literally. Keep dist[u] + w as the key and you compute a shortest-path tree, which is a different object - on many graphs heavier than the MST.
- Running it on a disconnected graph and not noticing the queue emptied early. Fewer than V vertices absorbed means no spanning tree exists.
- Pushing every edge of an absorbed vertex, including those leading back into the tree. They are guaranteed stale - filter at push time or discard on pop.
- Treating the MST as a shortest-path structure. Routes through a minimum spanning tree can be far longer than direct shortest paths - the tree minimises total weight, nothing else.
Where it is used
- Wiring and pipeline layout grown outward from an existing hub or depot.
- Maze generation: randomised Prim carves passages by absorbing random frontier walls.
- Dense-graph MST where an adjacency structure already exists and sorting all E edges would dominate.
- Prim vs Kruskal is itself a standard interview question - know the one-line difference from Dijkstra.
Frequently asked questions
What is the time and space complexity of Prim's algorithm?
O(E log V) with a binary heap: each edge is pushed at most once from each side, and every push or pop costs log V. Space is O(V) for tree membership and parent bookkeeping, plus the queue of pending candidate edges.
How is Prim different from Dijkstra?
One line - the priority. Dijkstra orders the queue by dist[u] + w, accumulated distance from the source, and produces a shortest-path tree. Prim orders it by w alone, the cost of crossing from tree to non-tree, and produces a minimum spanning tree. The loop is otherwise identical.
Does the choice of start vertex change the MST?
Never the total weight - the cut property holds from any seed, so this visualizer reaches 19 from any start node. The specific edges can differ only where equal weights let ties break differently; with distinct weights the MST is unique.
Prim vs Kruskal - when should I prefer Prim?
On dense graphs, where E approaches V² and Kruskal's O(E log E) sort dominates, and whenever an adjacency structure is already in memory. Prim also keeps one connected tree throughout, which some incremental applications want. On sparse edge lists Kruskal is usually simpler.