Prim's algorithm, explained

A minimum spanning tree connects every node in a graph using the least total edge weight, with no loops. Think of laying cable to connect several buildings as cheaply as possible.

Prim's algorithm builds it by starting from one node and growing outwards. At each step it adds the cheapest edge that connects the tree to a node that is not yet in it.

How it works

• Start with any one node in the tree.
• Look at all edges that join a tree node to a node outside the tree.
• Add the cheapest one, and the new node, to the tree.
• Repeat until every node is in the tree.

A small example

Take these weighted edges and start from A:

A-B:4  A-C:2  B-C:1  B-D:5  C-D:8  D-E:3

Edges added: A-C (2), C-B (1), B-D (5), D-E (3)
Total weight: 11

What to know about its cost

• O(V · E) as written in the experiment, and O(E log V) with a priority queue.
• Uses O(V) space.
• Needs an undirected, weighted graph.

Where it works well

• Works well on dense graphs.
• Grows one connected tree, which is easy to follow.

Where it struggles

• Needs a connected graph. Otherwise it only covers the nodes reachable from the start.
• The simple version is slower on big graphs than the version that uses a priority queue.

Try it yourself

Open the Graph Algorithms experiment, enter these edges (A-B:4, A-C:2, B-C:1, B-D:5, C-D:8, D-E:3), choose Prim's algorithm and start from A, and step through it. Then try a different graph and watch how the result changes.

Open the Graph Algorithms experiment