Problem — Growing a Network at Minimum Cost
Suppose we want to connect several cities using cables, roads, or pipelines. Each possible connection has a cost, and the goal is to connect every city while spending as little as possible.
In graph theory, this becomes a problem about finding a minimum spanning tree: a set of edges that connects all vertices, uses no cycles, and has the smallest possible total weight.
What is Prim’s algorithm?
Prim’s algorithm is a greedy method for finding a minimum spanning tree in a weighted graph. Instead of sorting all edges globally, it starts from one vertex and expands a single tree.
At each step, the algorithm looks at all edges leaving the current tree and selects the one with the smallest weight. The chosen edge must connect the tree to a new vertex outside the tree.
This process continues until all vertices are connected. If the graph has n vertices, the final spanning tree will contain exactly n − 1 edges.
The central intuition is simple: always extend the current tree using the cheapest possible edge.
Because it keeps growing one connected structure from the beginning, Prim is often one of the most intuitive algorithms for minimum spanning trees.
Why is this idea important?
Minimum spanning trees are useful whenever we want to build a connected structure at minimum cost: communication networks, road systems, electrical grids, transportation planning, and infrastructure design.
Prim’s algorithm is also important pedagogically because it shows how a local choice based on the current frontier can produce a globally optimal tree.
In practice, Prim is especially natural when we think of a network as something that grows outward from a chosen starting point.
Key intuition for Part 1
The goal is not merely to connect the graph — it is to connect it as cheaply as possible.
Prim achieves this by repeatedly asking: what is the smallest edge that can extend my current tree right now?
Unlike Kruskal, which examines edges in global order, Prim always works from the boundary of the tree already built.
In the next part, we will study the algorithm step by step, beginning from one starting vertex and following each accepted edge.