What you'll learn
A minimum spanning tree (MST) connects every vertex of a weighted graph using the cheapest total set of edges, with no cycles. It answers questions like "wire up all these cities with the least cable." Two classic greedy algorithms build it.
By the end you'll be able to:
- Define a spanning tree and a minimum spanning tree
- Build an MST with Kruskal's algorithm (and union-find)
- Contrast it with Prim's algorithm
Spanning trees
A spanning tree of a connected graph is a subset of edges that touches every vertex and forms a tree (connected, no cycles) — exactly V − 1 edges. The minimum spanning tree is the spanning tree with the smallest total edge weight. Both algorithms below are greedy, and both are provably optimal.
Kruskal's algorithm
Sort all edges by weight and add them cheapest-first, skipping any that would create a cycle. A union-find structure (Module 29) makes the cycle check nearly instant. Watch the forest of pieces merge into one tree:
Prim's algorithm
Prim's grows one tree from a starting vertex: repeatedly add the cheapest edge that connects the tree to a new vertex (using a priority queue of candidate edges). Kruskal thinks in terms of a growing forest of edges; Prim grows a single connected blob. Same MST, different strategy.
| Kruskal | Prim | |
|---|---|---|
Strategy | Cheapest edge overall (a growing forest) | Cheapest edge leaving the current tree |
Needs | Sorting + union-find | A priority queue |
Time | O(E log E) | O(E log V) |
Better for | Sparse graphs | Dense graphs |
In code
def kruskal(n, edges): # edges: list of (weight, u, v)
parent = list(range(n))
def find(x):
while parent[x] != x:
parent[x] = parent[parent[x]] # path compression
x = parent[x]
return x
mst, total = [], 0
for w, u, v in sorted(edges): # cheapest edges first
ru, rv = find(u), find(v)
if ru != rv: # no cycle
parent[ru] = rv # union
mst.append((u, v, w)); total += w
return mst, totalRecap & quick check
Key takeaways
- A minimum spanning tree connects all vertices with minimum total edge weight and no cycles (V−1 edges).
- Kruskal adds edges cheapest-first, skipping any that form a cycle.
- Union-find makes Kruskal's cycle check nearly O(1).
- Prim grows one tree, repeatedly adding the cheapest edge leaving it (via a priority queue).
- Both are greedy and both produce an optimal MST.
Quick check
1. A minimum spanning tree of a graph with V vertices has how many edges?
2. Kruskal's algorithm adds edges:
3. What structure makes Kruskal's cycle check efficient?
4. How does Prim's algorithm differ from Kruskal's?
Kruskal leaned on a structure that tracks connectivity almost for free. Let's build it. Next up: Module 29 — Union-Find (Disjoint Set).