Prim's Algorithm, step by step.

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

What is a minimum spanning tree (MST)?

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.

What is Prim's algorithm?

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.

How does Prim's algorithm work? The lightest edge out of the tree

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.

Prim's algorithm pseudocode with a priority queue

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.

Prim's algorithm example: the priority queue step by step

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.

Prim's algorithm on a weighted undirected graph

All steps as text
  1. Consider a weighted undirected graph. Build its minimum spanning tree.
  2. Start from vertex A and explore its neighboring vertices.
  3. Vertex A's neighbors are B and D.
  4. Use a priority queue to keep candidate edges ordered by weight.
  5. Check the weight of edge AB: 30.
  6. Enqueue edge AB in the priority queue according to its weight.
  7. Check the weight of edge AD: 79.
  8. Enqueue edge AD in the priority queue according to its weight.
  9. After examining its neighbors, mark vertex A as inspected.
  10. Dequeue the minimum-weight edge AB and add it to the growing spanning tree (highlighted in yellow).
  11. Inspect vertex B, which is in the growing spanning tree but has not yet been inspected.
  12. Uninspected neighbors of vertex B: C, D and E.
  13. Check the weight of edge BC: 95.
  14. Enqueue edge BC in the priority queue according to its weight.
  15. Check the weight of edge BD: 40.
  16. Since BD (40) is shorter than AD (79) and both lead to D, replace AD with BD in the queue.
  17. Replace AD with BD in the queue.
  18. Check the weight of edge BE: 27.
  19. Enqueue edge BE in the priority queue according to its weight.
  20. After examining its neighbors, mark vertex B as inspected.
  21. Dequeue the minimum-weight edge BE and add it to the growing spanning tree (highlighted in yellow).
  22. Inspect vertex E, which is in the growing spanning tree but has not yet been inspected.
  23. Uninspected neighbors of vertex E: C, D and F.
  24. Check the weight of edge EC: 14.
  25. Since EC (14) is shorter than BC (95) and both lead to C, replace BC with EC in the queue.
  26. Replace BC with EC in the queue.
  27. Check the weight of edge ED: 73.
  28. BD remains in the queue as the shorter edge to D, compared to ED.
  29. Check the weight of edge EF: 6.
  30. Enqueue edge EF in the priority queue according to its weight.
  31. After examining its neighbors, mark vertex E as inspected.
  32. Dequeue the minimum-weight edge EF and add it to the growing spanning tree (highlighted in yellow).
  33. Inspect vertex F, which is in the growing spanning tree but has not yet been inspected.
  34. Vertex F's only uninspected neighbor is C.
  35. Check the weight of edge FC: 36.
  36. EC remains in the queue as the shorter edge to C, compared to FC.
  37. After examining its neighbors, mark vertex F as inspected.
  38. Dequeue the minimum-weight edge EC and add it to the growing spanning tree (highlighted in yellow).
  39. Inspect vertex C, which is in the growing spanning tree but has not yet been inspected.
  40. Vertex C's only uninspected neighbor is D.
  41. Check the weight of edge CD: 89.
  42. BD remains in the queue as the shorter edge to D, compared to CD.
  43. After examining its neighbors, mark vertex C as inspected.
  44. Dequeue the minimum-weight edge BD and add it to the growing spanning tree (highlighted in yellow).
  45. Inspect vertex D, which is in the growing spanning tree but has not yet been inspected.
  46. Since all other vertices have already been inspected, the minimum spanning tree is successfully constructed.
  47. The minimum spanning tree has the edges AB, BE, EF, EC and BD, with a total weight of 30 + 27 + 6 + 14 + 40 = 117.
Prim's algorithm on a weighted undirected graph. Last step: The minimum spanning tree has the edges AB, BE, EF, EC and BD, with a total weight of 30 + 27 + 6 + 14 + 40 = 117.

Is Prim's algorithm greedy? The cut property proof

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.

Prim's algorithm time and space complexity: eager vs lazy

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 queueTimeExtra space
Adjacency matrix, plain arrayO(V2)O(V)
Adjacency list, binary heap, eagerO(E log V)O(V)
Adjacency list, binary heap, lazyO(E log V)O(E)
Adjacency list, Fibonacci heapO(E + V log V)O(V)

Prim vs Kruskal: which is better?

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 →

Prim vs Dijkstra: minimum spanning tree vs shortest path

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.

Prim's algorithm with negative weights, directed and disconnected graphs

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.

Prim's algorithm in Python, Java and C++

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++.

Applications of Prim's algorithm

  • Network design: joining sites by cable, pipe or road at the least total length.
  • Clustering: deleting a minimum spanning tree's k − 1 heaviest edges leaves the k clusters of single-linkage clustering.
  • Traveling salesman: when distances obey the triangle inequality, a walk round a minimum spanning tree that skips repeated vertices is at most twice the shortest tour.
  • Maze generation: randomized Prim takes a random candidate instead of the lightest, and the spanning tree of a grid's cells is a maze.
  • Interview problems: LeetCode 1584, Min Cost to Connect All Points, is a complete graph, where the O(V2) array version fits best.

Prim from A here.
Prim or Kruskal 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.

Four graphs, four trees

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.

Prim or Kruskal on your graph

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.

Spanning trees side by side

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).

Python, Java and C++

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.

Quiz

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 and Union-Find

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.

Spanning trees,
lightest edge out.

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