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 is defined for a weighted undirected connected graph and uses V−1 edges to minimize total connection cost. A disconnected graph has a minimum spanning forest instead. This is not a pairwise shortest-path objective.

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)

The cut property says that a minimum-weight edge crossing a cut is safe for at least one MST. With ties, a particular minimum edge need not belong to every MST. MST-based approximation guarantees for TSP require extra premises such as a complete metric graph satisfying the triangle inequality.

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