Minimum Spanning Trees: Connect Everything, Cheaply

"You have a town of houses and a price to lay cable between any pair. What's the cheapest wiring that reaches every house? That's a minimum spanning tree — and greedily grabbing the cheapest safe edges actually gives the optimal answer."

What an MST Is (and Isn't)

A minimum spanning tree of a weighted, connected graph is the cheapest set of edges that connects all the vertices — using exactly V−1 edges and forming a tree (no cycles). It answers 'what's the least-cost way to wire up the whole network?' Crucially, an MST is not about the shortest path between two specific nodes; it minimizes the total edge weight to keep everything connected. The route between two particular houses in an MST might be longer than necessary — that's fine, because the goal is cheap global connectivity, not fast point-to-point travel.

Kruskal's Algorithm: Cheapest Edges First

Kruskal's is beautifully greedy and reuses last lesson's tool: sort all edges by weight, then add them cheapest-first, skipping any edge whose two endpoints are already connected (that would form a cycle). 'Already connected?' is exactly the find question — so Union-Find is the engine: union the endpoints if they're in different sets, skip the edge if they share a root. Stop when you've added V−1 edges. The whole MST falls out of 'sort edges + union-find cycle check.' O(E log E) for the sort.

Prim's Algorithm: Grow From a Seed

Prim's takes the other angle: start from any one vertex and grow the tree outward, repeatedly adding the cheapest edge that connects the tree-so-far to a new vertex. 'Cheapest edge to a new vertex' is a min-heap query — so Prim's is to MST what Dijkstra is to shortest path, both powered by the priority queue from the Heaps track. Kruskal thinks in edges (sort them all); Prim thinks in growing a frontier (heap of crossing edges). Both produce a valid MST.

An MST connects all vertices with minimum total edge weight (V−1 edges, no cycle) — it's about cheapest global connectivity, NOT pairwise shortest paths. Kruskal's = sort edges + add cheapest non-cycle-forming (Union-Find); Prim's = grow from a seed via a min-heap. Greedy is provably optimal here.

Why Greedy Works Here (It Usually Doesn't)

Greedy algorithms are often wrong — grabbing the locally best choice frequently misses the global optimum (you'll see this fail in the Paradigms track). MST is one of the celebrated cases where greedy is provably correct, thanks to the cut property: for any way you split the vertices into two groups, the single cheapest edge crossing the split is always safe to include in some MST. Both Kruskal and Prim are just disciplined ways of always taking a cheapest crossing edge. Beyond wiring networks, MSTs power clustering (build the MST, then cut its k−1 most expensive edges to get k natural clusters) and approximate solutions to the traveling-salesman problem.

Pippa's Confession

I assumed greedy was always a shortcut that sometimes loses — grab-the-cheapest felt too naive to be optimal. Then Dad walked me through the cut property and I saw it: for MST, the greedy choice is guaranteed safe, not just usually. It reframed greedy for me — it's not inherently sloppy, it's a strategy that's correct exactly when a property like the cut property backs it. Knowing when greedy is provably right is the real skill, and MST is the cleanest example of it earning its keep.

Code

Kruskal's MST with Union-Find cycle checking·python

# Kruskal's MST, built on the Union-Find from the last lesson.
class UnionFind:
    def __init__(self, elems):
        self.parent = {e: e for e in elems}
    def find(self, x):
        while self.parent[x] != x:
            self.parent[x] = self.parent[self.parent[x]]   # path-halving
            x = self.parent[x]
        return x
    def union(self, x, y):
        rx, ry = self.find(x), self.find(y)
        if rx == ry: return False        # same set -> edge would make a cycle
        self.parent[ry] = rx
        return True

def kruskal(nodes, edges):
    """edges: list of (weight, u, v). Returns the MST edge list + total cost."""
    uf = UnionFind(nodes)
    mst, total = [], 0
    for w, u, v in sorted(edges):        # cheapest edges first
        if uf.union(u, v):               # only add if it connects two separate sets
            mst.append((u, v, w))
            total += w
    return mst, total

nodes = ["A", "B", "C", "D"]
edges = [(1,"A","B"), (3,"A","C"), (4,"B","C"), (2,"C","D"), (5,"B","D")]
mst, total = kruskal(nodes, edges)
print("MST edges:", mst)     # [('A','B',1), ('C','D',2), ('A','C',3)]
print("total cost:", total)  # 6 — cheapest way to connect all four, no cycles
# The 4-weight B-C edge is skipped: B and C are already connected via A.

Exercise

Run Kruskal's by hand on edges A-B(1), B-C(2), A-C(3), C-D(4). Sort them, add cheapest-first, and skip any that form a cycle — list the MST edges and total cost, and name the edge you skip and why. Then explain in one sentence how Union-Find tells Kruskal's that an edge would create a cycle.

Hint

Sorted: A-B(1), B-C(2), A-C(3), C-D(4). Add A-B, add B-C; A-C is skipped because A and C are already connected (same Union-Find root) — adding it would form a cycle. Add C-D. MST = {A-B, B-C, C-D}, total 7. Union-Find flags a cycle when find(u) == find(v).

What an MST Is (and Isn't)

Kruskal's Algorithm: Cheapest Edges First

Prim's Algorithm: Grow From a Seed

Why Greedy Works Here (It Usually Doesn't)

Pippa's Confession

Code

External links

Exercise

Progress

Comments 0