Prim's algorithm

Imagine laying cable from a power station: you connect the nearest town first, then whichever town is closest to anything already connected, and so on. That is Prim's algorithm, and it always ends with the cheapest possible network.

A graph with a tree growing from one node, the waiting nodes around it with their best edges drawn dashed, and the waiting nodes listed underneath
A graph with a tree growing from one node, the waiting nodes around it with their best edges drawn dashed, and the waiting nodes listed underneath

The idea

A minimum spanning tree connects every node of a weighted graph with the smallest possible total edge length. Prim's algorithm builds it by growing one tree outward from a start. The tree never splits into pieces: at every step, exactly one new node joins it, by the shortest edge that leads out of the tree.

Step by step

Put the start in the tree. For each node outside the tree, keep its best edge: its shortest edge to any node in the tree. Then repeat: pick the outside node whose best edge is the shortest, add it to the tree with that edge, and look at its edges. A neighbour outside the tree that can now be reached by a shorter edge gets that edge as its new best. Stop when every node is in the tree.

An example

Take the edges A–B of length 1, B–C 2, A–C 3, C–D 4 and B–D 5, and start at A. A's edges give B the best edge 1 and C the best edge 3. B is nearest, so it joins by A–B; its edges improve C to 2 and give D 5. C joins by B–C, and its edge C–D improves D to 4. Finally D joins by C–D. The tree A–B, B–C, C–D has total length 1 + 2 + 4 = 7.

Why it is right

At every step the nodes are split into two groups: those in the tree and those outside. The cut property says that the shortest edge between two such groups always belongs to some minimum spanning tree. Prim always adds exactly that edge, so the tree it has built so far can always be completed into a minimum spanning tree, and when every node has joined, it is one.

History and speed

The Czech mathematician Vojtěch Jarník published the algorithm in 1930. Robert Prim rediscovered it at Bell Labs in 1957, and Edsger Dijkstra again in 1959. With the waiting nodes in a binary heap, the work grows with E log V for V nodes and E edges; with a plain array it is about V², which is better when nearly every pair of nodes is joined. With a Fibonacci heap it is E + V log V.

Explore it

Open the app, click a node to start there, and press Step. Nodes in the tree are green, waiting nodes blue, and each waiting node's best edge is drawn dashed. The waiting nodes are listed under the graph with the length of their best edge, shortest first: the first one joins next. Start from different nodes and see the order change while the total stays the same.

Frequently asked questions

What is the difference between Prim's and Dijkstra's algorithm?

Both grow a region from a start using a priority queue. Prim ranks a waiting node by the length of its single best edge to the tree; Dijkstra ranks it by its whole distance from the start. Prim gives a minimum spanning tree, Dijkstra a tree of shortest paths.

Does Prim's algorithm work with negative edge lengths?

Yes. Unlike Dijkstra's algorithm, Prim only compares edges with each other, so negative lengths cause no trouble: it still finds a spanning tree with the smallest total.

What if the graph is not connected?

Then Prim's algorithm stops once it has reached every node it can: it gives a minimum spanning tree of the start's piece only. Running it again from a node not yet reached gives a minimum spanning forest.

Is Prim's or Kruskal's algorithm better?

Neither always wins. Prim suits dense graphs and graphs stored as lists of neighbours; Kruskal suits sparse graphs given as a list of edges. Both find a tree of the same total length.

Ready to try it?

Open PictorX in your browser — no install, no credit card required to start.

Try Prim's algorithm