Greedy Algorithms8 min read

MST — Greedy Lens

Connect all towns with the least road — always add the cheapest road that doesn't create a loop
Kruskal:\(O(E \log E)\)Prim (binary heap):\(O(E \log V)\)Prim (Fibonacci heap):\(O(E + V \log V)\)

Imagine you're a city planner connecting 10 remote towns with roads. Each possible road has a construction cost. You want every town connected to every other (directly or via other towns), and you want to spend as little total money as possible. What do you do?

Simple rule: always build the cheapest road that doesn't create a loop. A loop would mean you're paying for a redundant connection. Keep going until all towns are linked. That gives you the Minimum Spanning Tree — the cheapest possible network.

What Is a Spanning Tree?

A spanning tree of a connected graph with V vertices uses exactly V − 1 edges and connects all vertices with no cycles. The minimum spanning tree (MST) is the spanning tree with the lowest total edge weight. It's unique when all edge weights are distinct.

The Cut Property — Why Greedy Is Correct

Both MST algorithms are justified by the same theorem: the cut property.

A cut is any partition of vertices into two non-empty groups S and V\S. The cut property states: the minimum-weight edge crossing any cut is always part of some MST.

Why? Suppose the lightest crossing edge e were not in the MST. The MST still connects S to V\S, so some other edge e' crosses the cut. But e' is heavier than e. Swap e' for e — you get a lighter spanning tree, contradicting minimality of the MST. Contradiction.

Both Kruskal's and Prim's are simply different ways of repeatedly applying the cut property.

Kruskal's Algorithm

1. Sort all edges by weight ascending.
2. Go through edges in order. For each edge (u, v):
• If u and v are in different components → add this edge (it's the lightest edge crossing the cut between their components).
• If u and v are already connected → skip (adding it creates a cycle).
3. Stop when V − 1 edges are added.

Cycle detection is the key sub-problem. Union-Find solves it in nearly \(O(1)\) per edge: check find(u) == find(v). If equal, skip. If not, add the edge and union(u, v).

Total: \(O(E \log E)\) for sorting — Union-Find operations are nearly free.

Prim's Algorithm

1. Start from any vertex. Put it in the growing tree T.
2. Maintain a min-heap of edges leaving T (one endpoint in T, one outside).
3. Repeatedly extract the lightest such edge (u, v) where v is not yet in T. Add v (and the edge) to T. Push v's outgoing edges into the heap.
4. Stop when all vertices are in T.

This applies the cut property with S = current tree T at every step. The lightest edge from T to the rest is always safe to add.

With a binary heap: \(O(E \log V)\). With a Fibonacci heap: \(O(E + V \log V)\) — but Fibonacci heaps are complex to implement.

When to Use Each

Kruskal's is simpler to code and shines on sparse graphs (E close to V). Prim's with an adjacency matrix is better for dense graphs (E close to \(V^2\)) since you avoid sorting all edges. In competitive programming, Kruskal's + Union-Find is the go-to for most MST problems.

Note: Both algorithms are the same greedy idea viewed differently: Kruskal builds globally by adding the cheapest safe edge anywhere in the graph; Prim builds locally by expanding a single growing tree one vertex at a time. Both are justified by the cut property.

Kruskal's MST — Sort Edges + Union-Find

def kruskal(n, edges):
    # edges: list of (weight, u, v)
    edges.sort()
    parent = list(range(n))
    rank = [0] * n


    def find(x):
        while parent[x] != x:
            parent[x] = parent[parent[x]]
            x = parent[x]
        return x


    def union(a, b):
        ra, rb = find(a), find(b)
        if ra == rb: return False
        if rank[ra] < rank[rb]: ra, rb = rb, ra
        parent[rb] = ra
        if rank[ra] == rank[rb]: rank[ra] += 1
        return True


    mst_weight = 0
    mst_edges = []
    for w, u, v in edges:
        if union(u, v):
            mst_weight += w
            mst_edges.append((u, v, w))
    return mst_weight, mst_edges


# Graph: 4 vertices (0-3), edges as (weight, u, v)
edges = [(1,0,1),(2,0,2),(3,1,2),(4,1,3),(5,2,3)]
weight, mst = kruskal(4, edges)
print(f"MST weight: {weight}")
for u, v, w in mst:
    print(f"  {u} -- {v}  (weight {w})")
Output
MST weight: 7
  0 -- 1  (weight 1)
  0 -- 2  (weight 2)
  1 -- 3  (weight 4)

Complexity

🗂️ Kruskal — sort edgesDominant cost. Note: \(O(E \log E)\) = \(O(E \log V)\) since E ≤ \(V^2\)
Sort E edges\(O(E \log E)\)
⚡ Kruskal — Union-Find opsα is the inverse Ackermann function — effectively \(O(1)\) per operation
Nearly constant each\(O(E · α(V)\))
🌲 Prim — binary heapEach edge triggers at most one decrease-key on the heap
Sparse/medium graphs\(O(E \log V)\)
🚀 Prim — Fibonacci heapDecrease-key is \(O(1)\) amortized; rarely used in practice due to complexity
Theoretical optimum\(O(E + V \log V)\)
📐 MST output sizeAny spanning tree on V vertices has exactly V − 1 edges
Always V − 1 edges\(O(V)\)

Quick check

What is the cut property and why does it guarantee greedy MST algorithms are correct?

Continue reading

Greedy Pattern
Always grab the biggest slice of pizza — sometimes that's optimal, sometimes it isn't
→
Dijkstra's Algorithm
Always extend the cheapest road first — GPS navigation for graphs
→