- Current
- In the tree
- Next to the tree
- Best edge so far
Prim's algorithm
Prim's algorithm builds a minimum spanning tree, the cheapest set of edges that connects every node, by growing a single tree from a start. At every step it adds the node that can be reached by the shortest edge from the tree. Click a node to start there and step through to see the waiting nodes, their best edges, and the tree grow. Press Play to watch the tree grow, or Step and Back to go one step at a time. Drag the step slider to jump anywhere. Click a node to make it the start: the tree grows from there. The number on each edge is its length. Under the graph are the nodes waiting to join, each with the length of its best edge to the tree, which is drawn dashed. New graph makes another graph; choose how many nodes and edges it has. With the board selected, the arrow keys step, the space bar plays and pauses, and Home and End jump to the start and the end.
How it works
- Click a node to make it the start: the tree grows from there.
- Press Play, or use Step and Back to move one step at a time. Drag the step slider to jump anywhere.
- Watch the waiting nodes under the graph, each with its best edge to the tree. New graph makes another graph to try.
How Prim's algorithm works
Start with a tree of one node. Every node outside the tree remembers its shortest edge to the tree, if it has one. Repeatedly take the node whose edge is the shortest, add it and that edge to the tree, and look at its edges: if one is shorter than a neighbour's best edge so far, it becomes that neighbour's best edge. When every node has joined, the tree has one edge fewer than there are nodes, and its total length is as small as possible.
Prim and Dijkstra
Prim's algorithm and Dijkstra's algorithm look almost the same: both grow a region from a start and keep the waiting nodes in a priority queue. The difference is the number in the queue. Dijkstra keeps each node's whole distance from the start; Prim keeps only the length of its single best edge to the tree. So Dijkstra builds a tree of shortest paths, and Prim a tree of the smallest total length, and the two trees are often different.
Frequently asked questions
What is Prim's algorithm?
A greedy algorithm that builds a minimum spanning tree of a weighted graph by growing one tree from a start node, always adding the shortest edge that connects the tree to a node outside it.
Does the start node matter?
Only for the order: from any start, Prim's algorithm ends with a spanning tree of the same smallest total length. When some edges have equal lengths, the tree itself may differ.
Who invented Prim's algorithm?
Vojtěch Jarník described it first, in 1930. Robert Prim rediscovered it in 1957 and Edsger Dijkstra in 1959, so it is also called Jarník's algorithm or the Prim–Jarník algorithm.
How fast is Prim's algorithm?
With a binary heap, the work grows with E log V for V nodes and E edges. With a simple array instead of a heap it takes about V² steps, which is better for dense graphs where almost every pair of nodes is joined.
Is my graph sent anywhere?
No. The graph is made and the tree is built in your browser, and your last settings stay in this browser's local storage.
Ready to try it?
Open PictorX in your browser — no install, no credit card required to start.
Go to Editor