Prim
Prim starts from one vertex and keeps a single connected tree. At every step it takes the cheapest edge with one end inside the tree and the other outside, and adds that edge and its far end. The candidate edges live in a priority queue ordered by weight, so "cheapest edge leaving the tree" is one operation rather than a search.
Its frontier
A priority queue of the edges leaving the tree.
When it is the right choice
The same problem Kruskal solves, and the better choice when the graph is dense: Prim’s work is bounded by the edges leaving a growing tree rather than by sorting every edge in the graph. It is also the one to reach for when the tree has to stay connected as it grows — building outwards from a depot, say, rather than assembling pieces.
How it works
- Put the starting vertex in the tree.
- Put every edge leaving it into the priority queue.
- Take the cheapest edge in the queue.
- If both its ends are already in the tree, discard it: it would close a cycle.
- Otherwise add the edge and its far end to the tree, and queue every edge leaving that new vertex.
- Stop when the tree holds every reachable vertex.
Worth noticing
- The partial answer is always one connected piece, where Kruskal’s is several. Race them on the same graph: the total weight agrees at the end, and almost nothing agrees before it.
- An edge can sit in the queue and then be discarded when it comes out, because the far end joined the tree by another route in the meantime. The discarded count is how often that happened, and it is why the queue can hold more edges than the tree will ever use.
- Prim needs a starting vertex and Kruskal does not. On a disconnected graph that matters: Prim finds the tree of the component it started in, and nothing else.
Cost
- Best
- O(E log V)
- Average
- O(E log V)
- Worst
- O(E log V)
- Extra space
- O(V)
- Runs on
- a weighted undirected graph
- Largest grid
- 11 by 7 cells
- Largest graph
- 14 nodes, 28 edges
The limits are pedagogical rather than technical: this tool keeps a cost and a predecessor for every node in every recorded step, so the size of the graph sets the size of the trace directly, and a run has to stay short enough to sit and watch. A graph that would take more than three thousand steps on this algorithm is refused before a single step is generated, from a formula in the number of nodes and edges rather than by running it and finding out.
Graphs are generated from a seed, so the link in your address bar draws exactly the graph on your screen — no part of it is random in a way a reload could change.