26. Minimum Spanning Tree

What you'll learn

• 1Implement Union-Find with path compression and union by rank
• 2Implement Kruskal's algorithm
• 3Implement Prim's algorithm

Overview

An MST has V-1 edges and minimum total weight. Both Kruskal (E log E) and Prim ((V+E) log V) work. Union-Find (Disjoint Set Union) is a brilliant data structure for tracking connected components in O(α(N)) ≈ O(1) per operation.

Core Concepts

1. Union-Find

class UF:
    def __init__(self, n):
        self.parent = list(range(n + 1))
        self.rank = [0] * (n + 1)

    def find(self, x):
        while self.parent[x] != x:
            self.parent[x] = self.parent[self.parent[x]]   # path compression
            x = self.parent[x]
        return x

    def union(self, x, y):
        rx, ry = self.find(x), self.find(y)
        if rx == ry: return False        # same set
        if self.rank[rx] < self.rank[ry]:
            rx, ry = ry, rx
        self.parent[ry] = rx
        if self.rank[rx] == self.rank[ry]:
            self.rank[rx] += 1
        return True

2. Kruskal's algorithm

def kruskal(n, edges):
    """edges: list of (weight, u, v)"""
    edges.sort()
    uf = UF(n)
    total = 0
    used = 0
    for w, u, v in edges:
        if uf.union(u, v):
            total += w
            used += 1
            if used == n - 1: break
    return total if used == n - 1 else -1   # disconnected

3. Prim's algorithm

import heapq

def prim(n, adj):
    visited = [False] * (n + 1)
    heap = [(0, 1)]
    total = 0
    while heap:
        w, u = heapq.heappop(heap)
        if visited[u]: continue
        visited[u] = True
        total += w
        for v, nw in adj[u]:
            if not visited[v]:
                heapq.heappush(heap, (nw, v))
    return total

4. Which to use

• Kruskal: simpler when edges are easy to list. O(E log E).
• Prim: better for dense graphs. O((V + E) log V).
• For competitive programming, Kruskal + Union-Find is often the path of least resistance.

Examples

Example 1 — src/01_union_find.py

Union-Find with path compression and union-by-rank.

Example 2 — src/02_kruskal.py

Kruskal MST — BOJ 1197.

Example 3 — src/03_prim.py

Prim MST with heapq.

Example 4 — src/04_cycle_detect.py

Detect a cycle in an undirected graph using Union-Find.

Common Mistakes

1. Forgetting path compression in find() — degenerates to O(N) per op.
2. Adding an edge to MST without checking it forms a cycle.
3. Counting edges added — MST has exactly V-1.
4. Not handling disconnected input (no MST possible).

Recap

• MST: V-1 edges, minimum total weight.
• Kruskal: sort edges + Union-Find.
• Prim: grow from a seed with a heap.
• Union-Find: O(α(N)) amortized per op.

Try It

1. BOJ 1197 (MST).
2. BOJ 4386 (Constellation).
3. BOJ 1717 (Set operations) — pure Union-Find.