Home/Graphs/Prim
Search algorithmsCTRL K

Prim

· minimum spanning tree · grow from one node
/graphs/prim
IN TREE
1/ 10
nodes joined so far
TREE EDGES
0
chosen so far
TOTAL
0
weight of the tree
CROSSING
0
edges leaving the tree
LIGHTEST
—
weight of the chosen edge
candidatechosenin the treetree node
10 nodes · 11 edges · seed 7 · 20 steps
step 0 / 19
Nodes10
prim.ts
1
function prim(graph: Graph, start: Node) {
2
  const inTree = new Set([start]);
3
  const tree: Edge[] = [];
4
  while (inTree.size < graph.nodes.length) {
5
    let lightest: Edge | null = null;
6
    for (const edge of graph.edges) {
7
      if (inTree.has(edge.from) === inTree.has(edge.to)) continue;
8
      if (!lightest || edge.weight < lightest.weight) lightest = edge;
9
    }
10
    tree.push(lightest!);
11
    inTree.add(inTree.has(lightest!.from) ? lightest!.to : lightest!.from);
12
  }
13
  return tree;
14
}
CURRENT STEP
line 2

Start: the tree is just A. Total weight 0.

// how it works

Understanding Prim

Prim · always the lightest edge leaving the tree
01

The idea

Prim's algorithm builds a minimum spanning tree by growing it from one node. At each step it looks at every edge with exactly one endpoint in the tree, the crossing edges, and adds the lightest one together with its outside endpoint. After V − 1 additions every node is in the tree.

It is correct because of the cut property: the lightest edge crossing any cut belongs to some minimum spanning tree. The version shown scans all edges each round; the real one keeps the crossing edges in a heap, exactly like Dijkstra with the edge weight in place of the path length.

02

The four stages

1
startone node is the tree
2
scanedges with one endpoint inside
3
pickthe lightest crossing edge
4
growadd it and its outside node
03

Complexity

best
O(E log V)with a binary heap of crossing edges
average
O(E log V)the usual implementation
worst
O(V · E)this listing: scanning every edge per round
space
O(V + E)the tree set and the edges
04

Versus its siblings

EDGE SCANS · 1 000 NODES, 3 000 EDGES
prim, scan
3M
prim, heap
30,000
kruskal
33,000
borůvka
30,000
kruskal's cost is the sort · heap versions count log-factor operations
05

Pseudocode

PRIM(graph, source)
  tree ← {source}
  while tree does not span graph
    edge ← the lightest edge with one endpoint in tree
    add edge and its other endpoint to tree
06

When to use

Dense graphs, where E is close to V² and the heap version beats sorting all edges.
When the tree must be built from a given root, such as a network laid out from the central office.
07

Pitfalls

Disconnected graph: Prim only spans the component of the start node. Kruskal gives a forest.
Ties: equal weights can give different but equally minimal trees; do not compare trees, compare weights.
Scanning all edges each round is O(V · E); use a heap keyed by the lightest crossing edge per node.
08

History

Vojtěch Jarník published the algorithm in 1930 to lay out electricity lines in Moravia. Robert Prim rediscovered it at Bell Labs in 1957, and Edsger Dijkstra again in 1959 in the same paper as his shortest-path algorithm, which is why it is sometimes called the Prim–Jarník or DJP algorithm.

Back to Graphs