Minimum Spanning Trees

A Minimum Spanning Tree (MST) of a connected, weighted, undirected graph is a tree that:

1. Spans all V vertices (every vertex is included)
2. Uses exactly V - 1 edges
3. Has the minimum possible total edge weight

MSTs are guaranteed to exist for connected graphs and are unique if all edge weights are distinct.

Why MSTs Matter

The MST solves real problems: given N buildings, what is the cheapest set of cables that connects all of them? The answer is always an MST of the complete cost graph.

The Cut Property

Both Prim’s and Kruskal’s algorithms rely on the Cut Property: for any cut (partition of vertices into two sets), the minimum-weight edge crossing the cut is always in some MST. This greedy property is what makes both algorithms correct.

Kruskal’s Algorithm

Strategy: Process edges globally, sorted by weight. Add an edge if it doesn’t form a cycle.

Uses a Union-Find (DSU) data structure to detect cycles 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)

Time: O(E log E) for sorting + O(E · α(V)) for union-find ≈ O(E log E)

Best for: Sparse graphs where E is small

Prim’s Algorithm

Strategy: Grow the MST vertex-by-vertex. Always add the cheapest edge connecting the MST to a new vertex.

Start at A. key = {A:0, B:∞, C:∞, D:∞}

Extract A (key=0): Update neighbors: B→4, C→2
Extract C (key=2): Update neighbors: D→3, B→min(4,6)=4
Extract D (key=3): Update neighbors: B→min(4,5)=4
Extract B (key=4): MST complete

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

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

Best for: Dense graphs where E ≈ V²

Prim vs Kruskal

Union-Find (DSU)

Kruskal’s relies on Union-Find for O(α(V)) ≈ 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 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