Prim's algorithm finds a minimum spanning tree of a connected, weighted, undirected graph: starting from any vertex, it grows one tree, each time adding the lightest edge from the tree to a vertex not yet in it. With a binary heap as its priority queue it runs in O(E log V) time. This page explains how it works, with a step-by-step animation of Prim's algorithm and its priority queue on a weighted undirected graph from the VisiGrab app.
// how prim's algorithm works
A spanning tree of a connected, undirected graph includes every vertex, is connected and has no cycle. With V vertices it always has V − 1 edges. In a weighted graph, a minimum spanning tree is a spanning tree of least total weight. It is unique when all the weights differ; equal weights can allow several, all with the same total.
Prim's algorithm is a greedy algorithm that finds a minimum spanning tree of a connected, weighted, undirected graph and returns its V − 1 edges. It grows one tree from a start vertex, each step adding the lightest edge from the tree to a vertex outside it.
Vojtěch Jarník published it in 1930, Robert C. Prim rediscovered it in 1957 and Edsger W. Dijkstra in 1959, so it is also called Jarník's algorithm, Prim-Jarník or DJP.
Each vertex outside the tree has at most one candidate edge, the lightest found so far from the tree to it, and a priority queue holds the candidates, lightest first. This is the eager version, which the app runs.
1. Start: put any vertex in the tree. Another start changes the order in which edges join, not the total weight, nor the tree when all the weights differ.
2. Update the candidates: for each edge from the new tree vertex to a vertex outside, queue it as that vertex's candidate, or let it replace a heavier one.
3. Take the lightest candidate: remove it from the queue and add it to the tree with its far end, which goes through step 2 next.
4. Repeat until the tree has V − 1 edges.
Every edge taken leads to a vertex outside the tree, so no cycle can form: unlike Kruskal's algorithm, Prim needs no union-find, only a set of the vertices already in the tree.
The app's code builds the tree in buildMst. In pseudocode, with the Java listing's names shortened (find for findEdgeWithDestination, old for pqEdge):
pQ = EdgePriorityQueue(V)
inTreeSet = empty set
mst = empty list
current = startVertex
while size(inTreeSet) < V - 1
inTreeSet.add(current)
for each edge e from current
n = e.destination
if n in inTreeSet
continue
old = pQ.find(n)
if old is none
pQ.add(e)
else if old.weight > e.weight
pQ.replace(old, e)
if pQ is empty
return "disconnected"
edge = pQ.pollSmallest()
current = edge.destination
mst.add(edge)
return mst
find returns the queued edge to n, if any, and the test old.weight > e.weight lets only a strictly lighter edge replace it, which is decrease-key. The loop stops at V - 1 vertices in inTreeSet: the last vertex arrives with the final pollSmallest and has nothing left to examine. An empty queue before that means a disconnected graph, where the app's code throws an exception.
The player below runs Prim's algorithm from A on the app's default graph, with the priority queue on the right, lightest edge on top. The minimum spanning tree weighs 117. D enters the queue from A, by AD 79, and joins last, through BD 40, which replaced AD once B was in the tree.
A cut splits the vertices into two groups. By the cut property, the lightest edge crossing a cut belongs to a minimum spanning tree, and to every one when the weights differ. Prim's tree and the other vertices form a cut, and the lightest candidate is the lightest edge crossing it.
The proof is an exchange. If a minimum spanning tree lacks that edge e, adding e closes a cycle that crosses the cut again by an edge f at least as heavy. Swapping f for e gives a spanning tree that weighs no more, so it is minimum too, and it contains e.
So Prim's greedy choice is always safe. It is neither breadth-first nor depth-first search, whose queue and stack hand out the oldest or newest vertex where Prim's hands out the lightest edge, nor dynamic programming: it commits to each edge at once and keeps no table of subproblem answers.
The eager version keeps at most one entry per vertex outside the tree and lowers it when a lighter edge appears: the heap operation decrease-key. The lazy version queues every edge leaving the tree and skips one that comes out after its far end has joined. Its heap holds up to E edges, so it needs O(E) space, but as with Dijkstra's lazy deletion the time stays O(E log V).
With an adjacency matrix, scanning a plain array of candidate weights costs O(V) per step, O(V2) in all. On a dense graph, where E is close to V2, that beats a binary heap and matches a Fibonacci heap. By hand on a distance matrix, this is the decision maths table method: cross out each new vertex's row, then circle the smallest entry left in the tree's columns.
| Graph and queue | Time | Extra space |
|---|---|---|
| Adjacency matrix, plain array | O(V2) | O(V) |
| Adjacency list, binary heap, eager | O(E log V) | O(V) |
| Adjacency list, binary heap, lazy | O(E log V) | O(E) |
| Adjacency list, Fibonacci heap | O(E + V log V) | O(V) |
Kruskal's algorithm sorts the edges and takes each one that joins two separate trees, checked with union-find, so its trees stand apart until they merge, while Prim grows one tree from the start. Both find a minimum spanning tree, the same one when no two weights are equal; Prim's array version suits dense graphs, Kruskal sparse graphs and edge lists. Full comparison →
Dijkstra's algorithm runs the same loop, but keys a vertex by its total distance from the source, not by the one edge that joins it to the tree, and builds a shortest-path tree. In a triangle with AB 2, BC 2 and AC 3, the minimum spanning tree is AB and BC, of weight 4, while the shortest-path tree from A takes AB and AC, of weight 5: AC reaches C for 3, the route through B for 4.
Negative weights are fine: Prim only compares edges with each other. Adding a constant to every weight adds it V − 1 times to every spanning tree, so the minimum spanning tree stays the same, unlike shortest paths. With every weight negated, Prim finds a maximum spanning tree.
Directed graphs need the Chu-Liu/Edmonds algorithm, which finds a minimum spanning arborescence. On a disconnected graph Prim's queue runs empty early; restarting from an unreached vertex, once per component, gives a minimum spanning forest.
The app's listing runs the pseudocode above in all three languages, on a sorted array kept simple for clarity, so each lookup, add and replace costs O(V). Standard library heaps have no decrease-key, so code built on them usually runs the lazy version.
Note
For the eager version, Java's TreeSet and C++'s std::set, ordered by (weight, vertex), can drop a candidate and insert a lighter one in O(log V). Python's standard library has no ordered set, which leaves heapq and the lazy version. C++'s std::priority_queue needs std::greater to put the lightest edge first.
The full source code is on GitHub, in Python, Java and C++.
O(V2) array version fits best.// in the app
In VisiGrab, Prim's algorithm grows a minimum spanning tree on four example graphs, and every step shows its message and the priority queue of candidate edges changing beside the graph.
Besides this graph, the Examples dialog holds three more. In one, every new edge to a vertex already in the queue is lighter and replaces the queued one, five times over; in another, the second tree edge leaves A again; in a grid, one vertex finds all its neighbors already in the tree.
In the Graph Constructor, choose MST, draw an undirected graph of up to 12 vertices with weights from 1 to 99, tap Apply, then tap the start vertex. Each Next adds one tree edge and lists the edges so far; a switch runs Kruskal instead, and a disconnected graph is refused.
The info dialog sets six spanning trees of one small graph next to each other with their totals and marks the minimum in yellow. A second tab explains what makes Prim greedy and compares O(V²) with O(E log V).
The listing builds the tree with an in-tree set and an edge priority queue that swaps a queued edge for a lighter one to the same vertex. Four short notes cover tracking, the queue, edge handling and expansion, and the full source opens on GitHub.
Nine questions, every option explained: what a spanning tree is, which one is minimum, its n − 1 edges, ties, the edge Prim adds, greedy choice, the start vertex, why a priority queue, and what sets the running time.
Kruskal's algorithm has its own topic: it sorts the edges and skips any that would close a cycle. Union-Find, the structure it relies on for that check, has a topic too.
// build your own
Download VisiGrab to grow minimum spanning trees on four example graphs, then draw a weighted graph of your own, pick a start vertex and compare Prim with Kruskal.
Prim's algorithm is one of 30+ topics. See them all