Minimum Spanning Tree (Prim's)
DSA · Graphs
Theory
A minimum spanning tree (MST) connects all vertices of a weighted undirected graph using the minimum total edge weight, with no cycles. Prim's algorithm grows the tree from one starting vertex, always adding the cheapest edge that connects a vertex inside the tree to one outside it. With a priority queue it runs in O(E log V).
Why we use it
MSTs give the cheapest way to connect everything, such as laying cable or pipes.
When to use it
Use MSTs for network design, clustering, approximating travelling-salesman routes, and connecting cities or offices at minimum cost.
How it works
- Start from any vertex; heap of edges
- Pop the cheapest edge to an unvisited vertex
- Vertex already in tree? Yes: Skip. No: Add vertex and edge to tree.
- Push its edges to unvisited vertices
- Stop when all vertices are in the tree
Syntax
in_tree = {start}
while not all vertices in tree:
pick cheapest edge (u in tree, v outside)
add v and the edge
Time: O(E log V) with a heapExample
graph = {
"A": [("B", 2), ("C", 3)],
"B": [("A", 2), ("C", 1), ("D", 4)],
"C": [("A", 3), ("B", 1), ("D", 5)],
"D": [("B", 4), ("C", 5)],
}
def prim(start):
in_tree = {start}
chosen, total = [], 0
while len(in_tree) < len(graph):
best = None
for u in in_tree:
for v, w in graph[u]:
if v not in in_tree and (best is None or w < best[2]):
best = (u, v, w)
in_tree.add(best[1])
chosen.append(best)
total += best[2]
return chosen, total
edges, cost = prim("A")
print("MST edges:", edges)
print("Total cost:", cost)Key points
- Connects all vertices with minimum total weight
- Prim grows one tree from a start vertex
- Always picks the cheapest crossing edge
- Only for undirected weighted graphs