History
The method was first described by the Czech mathematician Vojtech Jarnik in 1930. Robert C. Prim independently published it in 1957, followed by Edsger W. Dijkstra in 1959. It is therefore sometimes called the Jarnik-Prim algorithm.
Graph algorithms / interactive lesson
Prim's Minimum Spanning Tree
Grow a minimum spanning tree one safe edge at a time. Watch the frontier change, inspect each greedy choice, and connect the cut property to a practical implementation.
High School
Guided lesson
Snapshot 1/12
Weighted undirected graph · cyan frontier · orange decision · green MST
Decision timeline
Start at node A
About the algorithm
Prim's algorithm constructs a minimum spanning tree: a connected backbone that reaches every vertex while keeping the total edge weight as small as possible. The result contains no cycles and always uses exactly V - 1 edges.
How it works
Begin with any vertex. Repeatedly inspect the frontier: edges with one endpoint inside the growing tree and one endpoint outside it. Add the cheapest frontier edge. The cut property guarantees that every such greedy choice is safe.
Where it is used
Prim's algorithm models low-cost network design: laying cables, connecting buildings, planning roads, wiring circuit boards, and constructing infrastructure backbones where every location must remain reachable.
Code companion
Connect each visual decision to an implementation pattern.
visited = { start }
tree = []
while visited does not contain every node:
frontier = edges with exactly one visited endpoint
edge = frontier edge with minimum weight
tree.add(edge)
visited.add(edge.unvisitedEndpoint)
return tree