Prim’s Algorithm
Building Roads Without Wasting Roads
How Prim’s Algorithm helps infrastructure planners connect locations at minimum cost
Imagine a government is planning a new road network connecting several villages, towns, and cities.
There are many possible roads that could be constructed. Some roads are short and inexpensive. Others pass through difficult terrain and cost much more.
The goal sounds simple:
Connect every important location while spending as little money as possible.
But building every possible road would be extremely expensive, while choosing roads randomly could leave some locations disconnected or create unnecessary construction costs.
This is where an algorithm from graph theory becomes surprisingly useful:
Prim’s Algorithm
Your Road Network Is Secretly a Graph
Think about a map containing cities and possible roads. Graph theory gives us a tidy way to describe it.
· Vertices (or nodes) represent cities, villages, towns, or other important locations.
· Edges represent possible roads connecting two locations.
· Weights represent construction cost, distance, time, or another measurable cost.
So instead of looking at a complicated infrastructure map, we get a clean mathematical model: locations + connections + costs.
Once the Map Becomes a Graph
Once we look at the road network this way, infrastructure planning becomes a precise question:
How do I connect every location while keeping the total construction cost as small as possible?
That is the type of problem solved by a Minimum Spanning Tree, or MST.
So, What Is a Minimum Spanning Tree?
A Minimum Spanning Tree connects all vertices of a connected, weighted, undirected graph without creating cycles, while minimizing the total weight of the selected edges.
So, What Is Prim’s Algorithm?
Prim’s Algorithm is a greedy algorithm used to find a Minimum Spanning Tree.
It starts from one vertex and repeatedly chooses the cheapest edge that connects the already-built tree to a new, unvisited vertex.
The road network grows outward one connection at a time.
Building Our Example Road Network
Let’s use five locations: A, B, C, D and E. Each letter represents a city, village, or infrastructure location
Start at A
Initially, only A belongs to our growing network.
Connected = {A}
The available roads are A–B with cost 4 and A–C with cost 2. The cheapest valid road is A–C.
Choose A–C
Cost = 2
Connected = {A, C}
Next, Look Outward
Now we inspect roads leaving A or C that lead to an unconnected location.
A–B = 4
C–B = 1
C–D = 8
C–E = 10
The cheapest is C–B with cost 1, so B is added.
Connected = {A, B, C}
Total cost = 2 + 1 = 3
Continuing the Construction
Step 3: Connect D
From the current network, the useful roads leading to an unconnected location include B–D = 5, B–E = 7, C–D = 8 and C–E = 10.
The cheapest choice is B–D.
Choose B–D
Cost = 5
Connected = {A, B, C, D}
Total cost = 8
Step 4: Connect E
Only E remains. The available roads include D–E = 2, B–E = 7 and C–E = 10.
The cheapest choice is D–E.
Choose D–E
Cost = 2
Connected = {A, B, C, D, E}
Total cost = 10
Final Road Network
A — — C
/ 1 8
/ B D
| |
5 2
|
E
Selected roads:
A–C = 2
C–B = 1
B–D = 5
D–E = 2
Total = 10
We connected five locations using four roads. Since V − 1 = 5 − 1 = 4, the result has exactly the number of edges expected in a spanning tree.
How Prim’s Algorithm Actually Works
The whole idea fits in one line:
Start at a vertex → find the cheapest edge leaving the current tree → add the new vertex → repeat.
In a little more detail
1. Choose a starting location.
2. Mark it as part of the MST.
3. Look at all edges from the current tree to unvisited vertices.
4. Choose the minimum-weight edge among them.
5. Add that edge and the new vertex.
6. Repeat until every vertex is included.
The Greedy Choice
Prim’s Algorithm is called greedy because it makes the cheapest locally available choice at every step.
Importantly, it does not simply choose the cheapest edge anywhere in the graph. It chooses the cheapest edge that expands the current tree to an unvisited vertex.
Current tree: A — C — B
Possible edges to new vertices:
B–D = 5
B–E = 7
C–D = 8
Choose B–D = 5
This rule keeps the selected edges connected and prevents cycles from being added to the growing tree.
A Python Version
import heapq
def prim(graph, start):
visited = set()
min_heap = [(0, start)]
total_cost = 0
mst = []
while min_heap:
cost, node = heapq.heappop(min_heap)
if node in visited:
continue
visited.add(node)
total_cost += cost
Get Bt’s stories in your inbox
Join Medium for free to get updates from this writer.
if cost != 0:
mst.append((node, cost))
for neighbour, weight in graph[node]:
if neighbour not in visited:
heapq.heappush(min_heap, (weight, neighbour))
return total_cost, mst
The Graph
graph = {
‘A’: [(‘B’, 4), (‘C’, 2)],
‘B’: [(‘A’, 4), (‘C’, 1), (‘D’, 5), (‘E’, 7)],
‘C’: [(‘A’, 2), (‘B’, 1), (‘D’, 8), (‘E’, 10)],
‘D’: [(‘B’, 5), (‘C’, 8), (‘E’, 2)],
‘E’: [(‘B’, 7), (‘C’, 10), (‘D’, 2)]
}
cost, mst = prim(graph, ‘A’)
print(“Minimum construction cost:”, cost)
print(“Selected roads:”, mst)
What the Important Parts Do
· `min_heap` keeps the smallest available road cost ready to be selected.
· `visited` records locations that are already part of the network.
· `heappop()` removes the cheapest available connection.
· `heappush()` adds newly discovered road options.
· `total_cost` keeps track of the construction cost.
Why Is This Useful in Road Construction?
Real infrastructure planning is obviously more complicated than our five-location example. But the mathematical core can be very similar.
Suppose a planning department has hundreds of possible road connections and each one has an estimated construction cost.
The network can be represented as:
Vertex = location
Edge = possible road
Weight = estimated construction cost
Prim’s Algorithm can then produce a minimum-cost connected structure for the given graph.
Construction Cost Is Not the Same as Distance
The edge weight does not have to mean physical distance.
· A 10 km road can cost more than a 15 km road if the terrain is difficult.
· Bridges can significantly increase construction cost.
· Land acquisition and labour can affect the estimate.
· Materials, elevation, environmental constraints, and maintenance can also influence cost.
Therefore, a more realistic model can use estimated construction cost as the edge weight rather than simply using distance.
One Important Limitation
An MST minimizes total connection cost. A real road network may need additional roads for traffic capacity, emergency access, alternate routes, public transport, and future development.
So an MST is best understood as a minimum-cost connectivity model, not a complete real-world transportation plan.
Prim’s Algorithm vs. Kruskal’s Algorithm
Prim’s Algorithm is not the only way to find a Minimum Spanning Tree. Kruskal’s Algorithm solves the same MST problem using a different strategy.
The Difference in One Sentence
Prim: “I already have a network. What is the cheapest road I can add next?”
Kruskal: “What is the cheapest road available that does not create a cycle?”
Prim vs. Dijkstra
Another common source of confusion is Dijkstra’s Algorithm.
How Fast Is Prim’s Algorithm?
The time complexity depends on the graph representation and data structure used.
Here V is the number of vertices and E is the number of edges.
For road planning, you can think of V as the number of locations and E as the number of possible road connections.
Why the Priority Queue Helps
A priority queue lets the algorithm quickly access the smallest available edge.
Possible costs:
10, 7, 5, 2
Minimum available road → 2
After the road is selected, new road options are inserted into the priority queue. This keeps the greedy selection efficient.
Space Complexity
When the graph is stored using adjacency lists, the graph itself requires O(V + E) space. The priority queue and visited structure add additional memory proportional to the graph being processed.
Where You’ll See This Idea
The same minimum-connectivity idea appears in many infrastructure and networking problems.
· Road construction — connect cities or villages with minimum construction cost.
· Railway planning — connect stations while minimizing track construction cost.
· Electrical grids — connect substations using minimum-cost transmission links.
· Water pipelines — connect areas using minimum-cost pipeline connections.
· Telecommunications — connect towers or network nodes with minimum infrastructure cost.
· Computer networks — connect devices while minimizing cable or link cost.
Road Network vs. Computer Network
The graph does not care what the vertices represent. It only sees vertices, edges, and weights.
Vertices + Edges + Weights
That is one of the most useful ideas in graph algorithms: the same mathematical structure can model very different real-world systems.
Common Misconceptions
“Prim’s Algorithm finds the shortest route between two cities.”
Not exactly. Prim finds a Minimum Spanning Tree for the entire graph. For shortest paths between two specific locations, algorithms such as Dijkstra’s Algorithm are more appropriate.
“Prim always chooses the globally cheapest road.”
Not exactly. It chooses the cheapest edge that connects the current MST to an unvisited vertex.
“The MST is automatically the best real-world road network.”
Not necessarily. Real infrastructure also considers traffic, safety, redundancy, population, geography, environmental impact, and future growth.
“Prim and Kruskal solve completely different problems.”
No. Both are used to find a Minimum Spanning Tree. Their strategies for constructing the tree are different.
Quick Check
1. What does a vertex represent in a road-construction graph?
2. What does the weight of an edge represent?
3. How many edges does an MST contain if there are 10 vertices?
4. What is the main greedy choice made by Prim’s Algorithm?
5. What is the time complexity of Prim’s Algorithm using a binary heap and adjacency list?
Answers
1. A vertex can represent a city, village, town, or another infrastructure location.
2. The edge weight can represent construction cost, distance, time, or another measurable cost.
3. V − 1 = 10 − 1 = 9 edges.
4. It chooses the minimum-weight edge that connects the current MST to an unvisited vertex.
5. O(E log V) for the standard adjacency-list + binary-heap implementation.
Final Takeaway
Road construction may look like a purely geographical problem, but underneath it can be represented as a graph.
Locations → Vertices | Roads → Edges | Costs → Weights
Prim’s Algorithm provides a systematic way to build a Minimum Spanning Tree, connecting every location while keeping the total connection cost as low as possible.
Its greedy strategy is simple: start somewhere, connect the cheapest possible new location, and keep expanding the network.
For infrastructure planning, this idea can provide a useful mathematical starting point for minimum-cost connectivity between cities, villages, railway stations, electrical substations, and other important locations.
But real infrastructure does not stop at minimum cost. Practical road planning must also consider traffic, safety, redundancy, environmental impact, and future growth.
So the key question Prim’s Algorithm helps answer is:
“What is the cheapest way to connect everything?”
References
1. GeeksforGeeks — Prim’s Algorithm for Minimum Spanning Tree.
2. Cormen, T. H., Leiserson, C. E., Rivest, R. L., and Stein, C. — Introduction to Algorithms.
3. Skiena, S. S. — The Algorithm Design Manual.
4. Python Documentation — heapq: Heap queue algorithm.
