Spanning Trees

A spanning tree of a connected, undirected graph includes every vertex and exactly V - 1 edges, connected with no cycles. Most connected graphs admit many spanning trees. A Minimum Spanning Tree (MST) is the spanning tree with the minimum possible total edge weight; it is unique when all edge weights are distinct. The MST is not a shortest-path tree: it minimizes total network cost, not distance from a single source.

Why MSTs Matter

The classic framing: given N sites and a cost for wiring each pair, what is the cheapest set of links that connects all of them? The answer is the MST of the complete cost graph. The same abstraction covers network design, cluster analysis, and approximation algorithms.

The Cut Property

For any partition of the vertices into two sets (a cut), the minimum-weight edge crossing the cut belongs to some MST. This is the fact that makes greedy MST algorithms correct. It is worth proving once to yourself: if the lightest crossing edge were left out, the MST must cross the cut somewhere with a heavier edge, and swapping in the lighter one still spans the graph and is cheaper.

Correctness Intuition

Both Prim and Kruskal are greedy, and the cut property is their shared license:

• Kruskal adds the globally lightest edge at each step that connects two different components (a “safe” edge).
• Prim grows one component, always taking the lightest edge that crosses the cut between the tree and the rest.

Because every added edge is the minimum edge across some cut, no added edge can be swapped for something cheaper — induction yields the global optimum.

Kruskal’s Algorithm

Strategy: process all edges globally in sorted order; add an edge unless it would create a cycle (its endpoints are already connected). Cycle detection uses Union-Find (DSU) in near-constant time:

Sort edges: A-B(1), B-C(2), C-D(3), A-C(4), B-D(5)

Process A-B(1): no cycle → ADD  MST: {A-B}
Process B-C(2): no cycle → ADD  MST: {A-B, B-C}
Process C-D(3): no cycle → ADD  MST: {A-B, B-C, C-D}
Done! (V-1 = 3 edges added)   total weight 6

Time: O(E log E) for the sort, plus O(E · α(V)) for union-find — total O(E log E).

Best for: sparse graphs where E is small.

Prim’s Algorithm

Strategy: grow a single tree vertex-by-vertex, always adding the cheapest edge connecting the tree to a new vertex. A priority queue holds candidate edges keyed by the minimum link to the growing tree:

Start at A: keys {A:0, B:∞, C:∞, D:∞}

Extract A (0)   → relax B→1, C→4
Extract B (1)   → relax C→min(4,2)=2, D→5
Extract C (2)   → relax D→min(5,3)=3
Extract D (3)   → MST complete

MST edges: A-B(1), B-C(2), C-D(3) — total weight 6

Time: O((V + E) log V) with a binary heap.

Best for: dense graphs where E ≈ V²; it never needs to sort the full edge set.

Comparison: Prim vs Kruskal

Union-Find (DSU)

Kruskal’s relies on Union-Find for its near-O(1) cycle detection:

find(x):  # with path compression
    if parent[x] != x:
        parent[x] = find(parent[x])
    return parent[x]

union(x, y):  # with union by rank
    px, py = find(x), find(y)
    if px == py: return False  # same component = cycle
    if rank[px] < rank[py]: parent[px] = py
    else: parent[py] = px
    return True

Applications

• Network design — laying cable, fiber, or roads to connect all sites at minimum cost.
• Clustering — run Kruskal, then cut the k - 1 heaviest edges to split the MST into k clusters.
• Approximation algorithms — the MST is the first step of the 2-approximate traveling-salesman tour.
• Facility connection, VLSI routing, image segmentation — any “connect everything cheaply” problem.

Worked Example

Connect four sites A, B, C, D with edge costs A-B(1), B-C(2), C-D(3), A-C(4), B-D(5).

Kruskal sorts the edges and adds A-B(1), B-C(2), C-D(3); A-C and B-D are skipped because they would close a cycle. Total weight = 6.

Prim from A extracts A(0), then B(1), then C(2), then D(3), always taking the cheapest link from the growing tree: A-B, B-C, C-D. Total weight = 6.

Both algorithms produce the same tree — the unique MST, since all weights are distinct — and both reach the same optimal total of 6. That agreement is the cut property in action.

Practice Trajectory

1. Implement Union-Find with path compression and union by rank; test cycle detection on a small graph.
2. Implement Kruskal and verify the edge count is always V - 1 and the total is minimal on random graphs.
3. Implement Prim with a binary heap and confirm both algorithms produce equal-weight MSTs on dense graphs.
4. Cut the k - 1 heaviest MST edges and check the resulting clusters against hand-labeled expectations.
5. Prove the cut property on a 5-vertex graph: try to find a cut whose lightest edge is not in your MST — then explain why it cannot exist.

When It’s the Right Tool