Minimum Spanning Trees (Kruskal's & Prim's)

What a spanning tree is, and why "minimum" matters

A spanning tree of a connected, undirected graph is a subset of its edges that connects every vertex, using the fewest possible edges to do so (exactly V − 1 edges for V vertices) — and, being a tree, contains no cycles. Many graphs have MANY different spanning trees; if edges are weighted, the Minimum Spanning Tree (MST) is the one whose edges sum to the smallest total weight. This is well-defined only for graphs that are connected (otherwise no single tree can reach every vertex) and undirected (an MST's edges don't have a direction — "connect A and B as cheaply as possible" is symmetric).

Picture a town planner connecting a set of villages with roads, where each possible road between two villages has its own construction cost, and the planner's job is to make sure every village can reach every other village — by SOME path, not necessarily a direct road — while spending as little as possible on construction in total. There's no reason to ever build a road that closes a loop back to a village already reachable another way; every dollar spent on a redundant road is a dollar that connected nothing new. That's an MST: the cheapest possible road network that still leaves every village reachable from every other.

This module presents two classic MST algorithms, both greedy, both provably correct via the same underlying fact (the cut property, below) — but built on different data structures and suited to different graph shapes.

The cut property: why greedy works here at all

A cut is any partition of the vertices into two non-empty groups. A crossing edge is an edge with one endpoint in each group — split the villages into any two regions you like, and a crossing road is any road that would connect a village in one region to a village in the other. The cut property states: for any cut of the graph, the minimum-weight crossing edge is part of SOME minimum spanning tree (assuming all edge weights are distinct, for simplicity of statement — ties can be broken consistently without changing the argument). In town-planning terms: no matter how you split the villages into two regions, the cheapest road that COULD bridge those two regions belongs in some optimal network — there's never a reason to pay more than necessary to connect two regions that need connecting at all.

Why: suppose, for contradiction, that the minimum-weight crossing edge e were NOT in some particular MST T. Since T connects every vertex, it must contain some OTHER edge e' crossing the same cut (any spanning tree must cross every cut at least once, or the two groups wouldn't be connected to each other). Since e is the minimum-weight crossing edge, weight(e) < weight(e'). Swap e' out of T and e in — this produces another spanning tree (removing e' splits T into two pieces exactly along the cut, and adding e reconnects them, since e also crosses the same cut) with strictly LOWER total weight than T. This contradicts T being minimum. So the minimum crossing edge must have been in an MST all along. This is the exchange argument from the Greedy module's concept lesson, applied concretely to spanning trees.

Both algorithms below are just different strategies for repeatedly finding a cut and taking its minimum crossing edge, in an order that's convenient to compute.

Kruskal's algorithm: sort edges, add if no cycle

Kruskal's algorithm processes ALL edges globally, sorted by weight from smallest to largest, greedily adding each edge to the growing MST unless it would create a cycle (which would mean both its endpoints are already connected within the MST-so-far — adding it wouldn't connect anything new, only waste weight on a redundant edge). This is a planner working from a master list of every possible road in the region, cheapest first, building each one unless its two villages are already reachable from each other by roads already built — building that road would only create a second, wasted route between two villages that don't need one.

The "would this edge create a cycle" check is exactly what Union-Find (previous lesson) answers efficiently: two endpoints are already connected if and only if find(u) == find(v). Skip the edge if so; otherwise, union(u, v) and add the edge to the MST.

def kruskal_mst(num_vertices: int, edges: list[tuple[int, int, int]]) -> int:
    # edges: list of (weight, u, v) — sorted below by weight.
    edges = sorted(edges, key=lambda e: e[0])
    uf = UnionFind(num_vertices)          # from the Union-Find concept lesson
    total_weight = 0
    edges_used = 0

    for weight, u, v in edges:
        if uf.find(u) != uf.find(v):      # would NOT create a cycle
            uf.union(u, v)
            total_weight += weight
            edges_used += 1
            if edges_used == num_vertices - 1:   # MST is complete
                break

    return total_weight

Why this is correct, via the cut property: processing edges in increasing weight order means that whenever an edge (u, v) is considered and u, v are in different components (different Union- Find groups), that edge is provably the minimum-weight edge crossing the cut "u's current component vs. everything else" — because every smaller-weight edge has already been processed, and none of them connected u's component to v's (or they'd already be the same component). The cut property guarantees this edge belongs in an MST, so adding it is always safe.

Prim's algorithm: grow one tree from a single vertex

Prim's algorithm builds the MST differently: start from any single vertex, and repeatedly add the minimum-weight edge that connects the GROWING TREE to any vertex not yet in it — always extending the same single connected tree, rather than Kruskal's approach of considering edges globally regardless of which component they're in. In town-planning terms: instead of working from a master list of every possible road in the region, the planner starts at one village and keeps building whichever cheapest road reaches a brand-new village next, growing one connected network outward from that starting point rather than shopping the whole region's road list at once.

This is structurally the same shape as Dijkstra's algorithm (previous lesson): a priority queue of "frontier" edges, repeatedly popping the minimum and, if it reaches a new vertex, adding it to the tree and pushing its outgoing edges. The difference: Dijkstra relaxes by comparing PATH DISTANCE FROM THE SOURCE (dist[u] + weight), while Prim's compares the SINGLE EDGE WEIGHT directly (no accumulation) — Prim's is asking "what's the cheapest way to reach a new vertex from the tree so far," not "what's the cheapest total path from the start."

import heapq

def prim_mst(num_vertices: int, adj: list[list[tuple[int, int]]]) -> int:
    # adj[u] = list of (neighbor, weight) — the weighted adjacency list.
    visited = [False] * num_vertices
    heap = [(0, 0)]                    # (edge weight to reach this vertex, vertex) — start at 0
    total_weight = 0

    while heap:
        weight, u = heapq.heappop(heap)
        if visited[u]:
            continue                    # stale entry — u already joined the tree
        visited[u] = True
        total_weight += weight
        for v, w in adj[u]:
            if not visited[v]:
                heapq.heappush(heap, (w, v))   # cost is the RAW edge weight, not accumulated

    return total_weight

Why this is correct, also via the cut property: at every step, the cut is "the tree built so far vs. everything else." Popping the minimum-weight edge crossing that exact cut and adding its new endpoint is precisely the cut property's guarantee applied with the tree-so-far as one side of the cut — so, just like Kruskal's, every edge Prim's adds is provably part of some MST.

Kruskal vs. Prim: which wins when

Both run close to O(E log E), and it's worth seeing where each factor comes from rather than taking it on faith. Kruskal's is dominated by the upfront sort: comparison sorting E edges costs O(E log E), and the Union-Find operations that follow (E of them, one find/union pair per edge, each amortized O(α(V)) from the previous lesson) add only a lower-order term. Since a simple graph has at most V² edges, E ≤ V², so log E ≤ log(V²) = 2 log V — the 2 is a constant factor Big O discards, which is why this is often written O(E log V) instead. Prim's total is the same shape for a different reason: with a binary heap, each of the V vertices is extracted at most once (O(log V) per extraction) and each of the E edges triggers at most one heap push (O(log V) per push) — summing V extractions and E pushes, both costing O(log V) each, gives O((V + E) log V), which for a connected graph (E ≥ V − 1) simplifies to O(E log V) — the same reasoning as Dijkstra in the previous lesson. The practical difference is in how each accesses the graph:

• Kruskal's processes edges GLOBALLY and needs them sorted upfront — natural when the graph is given as an edge list, and efficient on sparse graphs (E close to V) since sorting a small edge list is cheap and Union-Find operations are near-constant.
• Prim's grows outward from a vertex using the adjacency representation directly, never needing to look at the whole edge set at once — natural when the graph is given (or can cheaply be treated) as an adjacency list, and preferred on dense graphs (E close to V²) since it avoids ever materializing and sorting the full, potentially huge, edge list that Kruskal's requires upfront.