Prim's Algorithm
A greedy algorithm that finds a minimum spanning tree for a weighted undirected graph.
Visualization
Details
Analogy
Imagine you need to install a cable network to connect several houses in a neighborhood. You want to use the minimum amount of cable. Prim's algorithm is like starting at one house, then connecting it to its absolute closest neighbor. Now, from this two-house network, you find the next closest house to *either* of the connected houses and add that connection. You always add the cheapest possible connection from your existing network to a new, unconnected house, until all houses are connected.
Purpose
To find a subset of the edges of a connected, edge-weighted undirected graph that connects all the vertices together, without any cycles and with the minimum possible total edge weight.
Use Cases
Designing networks (like telecommunications, water supply, electrical grids) to be as cost-efficient as possible. Also used in network routing and pathfinding.
Algorithm Steps
initialize visited set and priority queue
add start vertex with weight 0 to queue
while queue not empty:
pop vertex with minimum weight
if vertex already visited: continue
mark vertex as visited
add edge to MST
for each neighbor of vertex:
if neighbor not visited:
add neighbor to queue with edge weight
return MST
Explanation
What's Happening?
Start at node A. Add its edges (A-B weight 2, A-D weight 6) to a priority queue.
Code Implementation
import heapq
def prim(graph, start_node):
mst = []
visited = {start_node}
edges = [
(weight, start_node, neighbor)
for neighbor, weight in graph[start_node].items()
]
heapq.heapify(edges)
while edges:
weight, u, v = heapq.heappop(edges)
if v not in visited:
visited.add(v)
mst.append((u, v, weight))
for neighbor, weight in graph[v].items():
if neighbor not in visited:
heapq.heappush(edges, (weight, v, neighbor))
return mst