Understanding Algorithms (Optimization Structures), Part 22: Prim’s Algorithm.
Prim’s Algorithm is a greedy graph algorithm used to build a Minimum Spanning Tree (MST) by growing it one vertex at a time. Unlike shortest-path algorithms that focus on reaching destinations, Prim’s Algorithm focuses on connecting all nodes while keeping the total edge weight as small as possible. It operates on connected, weighted, undirected graphs and guarantees an optimal result as long as these conditions are met.
The core idea behind Prim’s Algorithm is simple. Start from any vertex. Then repeatedly attach the cheapest edge that connects a vertex already in the tree to a vertex outside the tree. Each step expands the current spanning tree until every vertex has been included. This process continues until exactly V − 1 edges have been selected, where V is the number of vertices.
Prim’s Algorithm maintains two logical sets: vertices that are already part of the MST and vertices that are not. At every iteration, the algorithm scans edges that cross this boundary and chooses the minimum-weight edge. This choice is safe because of the cut property of Minimum Spanning Trees, which guarantees that the smallest edge crossing any cut must belong to at least one MST. This is what makes the greedy approach valid.
In implementation, Prim’s Algorithm usually tracks for each vertex the current minimum cost required to connect it to the growing tree. A priority queue (min-heap) is commonly used to efficiently select the next vertex with the smallest connecting edge. Initially, all vertices are assigned infinity cost except the starting vertex, which is set to zero. The algorithm then repeatedly extracts the minimum-cost vertex, marks it as visited, and updates its neighboring vertices if a cheaper connection is found.
The steps can be summarized as follows: initialize all keys to infinity, choose a starting vertex with key zero, push all vertices into a priority queue, repeatedly extract the vertex with minimum key, and relax all adjacent edges. Each relaxation checks whether a neighbor can be connected with a smaller edge weight than previously recorded. If so, its key is updated in the priority queue.
Get the computer science teacher’s stories in your inbox
Join Medium for free to get updates from this writer.
Time complexity depends on the data structures used. With an adjacency list and binary heap, Prim’s Algorithm runs in O(E log V). Using a Fibonacci heap improves this to O(E + V log V), though this is rarely used in practice due to implementation complexity. With an adjacency matrix, Prim runs in O(V²), which is acceptable for dense graphs but inefficient for sparse ones.
One important characteristic of Prim’s Algorithm is that it is vertex-oriented. It grows outward from a starting node, unlike Kruskal’s Algorithm, which is edge-oriented and works globally by sorting edges first. Because of this, Prim’s feels structurally similar to Dijkstra’s Algorithm. Both use priority queues, both expand from a source, and both update neighboring nodes through relaxation. The difference is conceptual: Dijkstra minimizes path distances from a source, while Prim minimizes total tree cost across all vertices.
Prim’s Algorithm does not depend on edge direction and assumes the graph is connected. If the graph is disconnected, Prim will only generate an MST for the connected component containing the start vertex. In such cases, running Prim separately on each component produces a Minimum Spanning Forest.
In practical systems, Prim’s Algorithm is used in network layout, circuit design, and infrastructure planning, where the objective is to connect many entities with minimal wiring or cost. Its incremental nature makes it suitable for scenarios where the graph is already stored as adjacency lists and where edges are discovered dynamically.
Conceptually, Prim’s Algorithm teaches how greedy expansion can construct globally optimal structures. It demonstrates how local minimum choices, when backed by mathematical guarantees, lead to correct solutions. It also reinforces the importance of priority queues and graph representations in real algorithm implementations.
Prim’s Algorithm turns the abstract idea of Minimum Spanning Trees into a concrete construction process. Starting from a single node and repeatedly adding the cheapest safe edge shows how large systems can be built step by step, always choosing the next best connection, until everything becomes part of one efficient, cycle-free structure.
import heapq
class PrimsAlgorithm:
def __init__(self):
"""
Initializes Prim’s Algorithm.
What this algorithm does:
- Builds Minimum Spanning Tree.
- Grows from a starting vertex.
- Always picks the cheapest connecting edge.
Core idea:
- Greedy expansion.
- One growing tree.
"""
pass
# --------------------------------------------------
# BUILD GRAPH (ADJACENCY LIST)
# --------------------------------------------------
def build_graph(self, edges):
"""
Converts edge list into adjacency list.
Why:
- Allows fast neighbor lookup.
- Required for Prim’s traversal.
"""
graph = {}
for u, v, w in edges:
if u not in graph:
graph[u] = []
if v not in graph:
graph[v] = []
graph[u].append((v, w))
graph[v].append((u, w))
return graph
# --------------------------------------------------
# PRIM'S MST ALGORITHM
# --------------------------------------------------
def prim(self, graph, start):
"""
Executes Prim’s Algorithm.
Strategy:
- Start from one node.
- Push all outgoing edges to priority queue.
- Always choose minimum weight edge.
- Expand tree step by step.
Heap ensures:
- Cheapest edge is always chosen first.
"""
visited = set()
min_heap = [(0, start, None)]
mst = []
total_cost = 0
while min_heap:
weight, current, parent = heapq.heappop(min_heap)
# Skip already visited nodes
if current in visited:
continue
visited.add(current)
total_cost += weight
if parent is not None:
mst.append((parent, current, weight))
# Push neighbors
for neighbor, cost in graph[current]:
if neighbor not in visited:
heapq.heappush(min_heap, (cost, neighbor, current))
return mst, total_cost
# --------------------------------------------------
# EXAMPLE USAGE
# --------------------------------------------------
edges = [
('A', 'B', 1),
('A', 'C', 4),
('B', 'C', 2),
('B', 'D', 5),
('C', 'D', 3)
]
prims = PrimsAlgorithm()
graph = prims.build_graph(edges)
mst, cost = prims.prim(graph, 'A')
print("Edges in Minimum Spanning Tree:")
for edge in mst:
print(edge)
print("Total Cost:", cost)
