Minimum Spanning Trees — Algorithms Course

What you'll learn

A minimum spanning tree (MST) connects every vertex of a weighted graph at the lowest total edge cost — the cheapest network that links everything. Two classic greedy algorithms find it: Prim's and Kruskal's.

By the end you'll be able to:

State the cut property that makes greedy MST work
Build an MST with Prim's and Kruskal's
Use union-find to detect cycles in Kruskal

Spanning trees & the cut property

A spanning tree connects all V vertices with exactly V − 1 edges and no cycles. The minimum one has the least total weight. Both algorithms rely on the cut property: for any way of splitting the vertices into two sides, the cheapest edge crossing the split is safe to include in some MST. Greedily adding safe edges builds the whole tree.

Prim's algorithm

Prim grows a single tree from a start vertex, always adding the cheapest edge leaving the tree (via a priority queue). Watch the tree expand edge by cheapest edge:

Prim's MST from A

Prim's minimum spanning tree

4352671

1/12Prim's MST from A: grow a tree, always adding the cheapest edge that leaves it.

Grow one tree, each step adding the lightest edge that reaches a new vertex.

Language

prim.py

import heapq

def prim(adj, start):              # adj[u] = [(v, w), ...]
    visited = {start}
    pq = [(w, start, v) for v, w in adj[start]]
    heapq.heapify(pq)
    mst, total = [], 0
    while pq:
        w, u, v = heapq.heappop(pq)
        if v in visited:
            continue               # would form a cycle
        visited.add(v)
        mst.append((u, v, w)); total += w
        for nb, nw in adj[v]:
            if nb not in visited:
                heapq.heappush(pq, (nw, v, nb))
    return mst, total

Kruskal & union-find

Kruskal takes the opposite view: consider all edges cheapest-first, adding each one that doesn't create a cycle — building a forest that merges into one tree. The cycle check is what union-find (disjoint-set) does in near-constant time: find returns a vertex's set representative, and union merges two sets. Path compression keeps trees flat:

Language

kruskal.py

def kruskal(n, edges):             # edges = [(w, u, v)]
    parent = list(range(n))
    def find(x):
        while parent[x] != x:
            parent[x] = parent[parent[x]]   # path compression
            x = parent[x]
        return x
    mst, total = [], 0
    for w, u, v in sorted(edges):  # cheapest edge first
        ru, rv = find(u), find(v)
        if ru != rv:               # different trees -> no cycle
            parent[ru] = rv        # union
            mst.append((u, v, w)); total += w
    return mst, total

Key idea

Union-find with path compression and union by rank runs each operation in O(α(n)) — inverse-Ackermann, effectively constant. It's the secret behind Kruskal's O(E log E) (dominated by the sort) and shows up all over connectivity problems.

Prim vs Kruskal

	Prim	Kruskal
`Strategy`	Grow one tree from a vertex	Add cheapest edges, avoid cycles
`Core structure`	Priority queue	Union-find + sort
`Time`	O((V+E) log V)	O(E log E)
`Best for`	Dense graphs	Sparse graphs / edge lists

Recap & quick check

Key takeaways

An MST connects all vertices with V−1 edges at minimum total weight.
The cut property: the cheapest edge crossing any cut is safe for some MST.
Prim grows one tree via a priority queue (cheapest edge leaving the tree).
Kruskal adds cheapest edges, skipping cycles — using union-find to detect them.
Union-find with path compression + union by rank is near-constant per operation.

Quick check

1. How many edges does a spanning tree of V vertices have?

2. What does Prim's algorithm add at each step?

3. What does Kruskal use to detect cycles?

4. Union-find with path compression and union by rank runs each op in:

Shortest paths and MSTs move things along a network. Next: how much can flow through one. Next up: Module 28 — Network Flow.