Minimum Spanning Tree

You're a city planner. You have V cities and E possible roads, each with a construction cost. You want every city to be reachable from every other city, but you want to minimize the total road cost. You also want no redundant roads — no cycles.

The result is a Minimum Spanning Tree (MST): a subset of exactly V-1 roads that connects all V cities with the minimum possible total weight.

Kruskal's Algorithm

Kruskal's greedy insight: always pick the cheapest available road that doesn't create a cycle. Sort all roads by cost, then greedily add them one by one, skipping any road that would form a loop.

Union-Find detects cycles in \(O(α(n)\)) per check — making Kruskal's very efficient.

pseudocode

function kruskal(cities, roads):
  sort roads by weight ascending
  uf = UnionFind(cities)
  mst = []

  for (cityA, cityB, cost) of roads:
    if find(cityA) !== find(cityB):  // no cycle!
      union(cityA, cityB)
      mst.push((cityA, cityB, cost))
    if mst.length === cities.length - 1: break

  return mst

Prim's Algorithm

Prim's builds the MST by growing a connected cluster one city at a time. Start with any city. Always add the cheapest road that connects the current cluster to a new city. Use a min-heap to efficiently find the cheapest connecting road.

pseudocode

function prim(graph, start):
  inMST = {start}
  heap = min-heap of (cost, neighbor) from start
  mst = []

  while heap not empty and inMST.size < V:
    (cost, city) = heap.pop()  // cheapest connecting road
    if city in inMST: continue
    inMST.add(city)
    mst.push(city)
    for (neighbor, weight) of graph[city]:
      if neighbor not in inMST:
        heap.push((weight, neighbor))

  return mst

Kruskal's vs Prim's

Both always produce a valid MST. Kruskal's shines on sparse graphs (few roads) — sorting E edges is cheap when E is small. Prim's shines on dense graphs — the heap only tracks border edges, not all of them.

Kruskal's MST Algorithm

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

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

    def union(x, y):
        px, py = find(x), find(y)
        if px == py: return False
        if rank[px] < rank[py]: px, py = py, px
        parent[py] = px
        if rank[px] == rank[py]: rank[px] += 1
        return True

    edges.sort()
    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

edges = [(1,0,1),(3,0,2),(4,1,2),(2,1,3),(5,2,3)]
weight, mst = kruskal(4, edges)
print(weight)  # 6
print(mst)     # [(0, 1, 1), (1, 3, 2), (0, 2, 3)]

Output

6
[(0, 1, 1), (1, 3, 2), (0, 2, 3)]

Prim's MST Algorithm

import heapq

def prim(graph, start=0):
    """graph: adjacency list {node: [(neighbor, weight)]}"""
    visited = set()
    heap = [(0, start, -1)]  # (weight, node, parent)
    mst_weight = 0
    mst_edges = []
    while heap:
        w, node, parent = heapq.heappop(heap)
        if node in visited: continue
        visited.add(node)
        mst_weight += w
        if parent != -1: mst_edges.append((parent, node, w))
        for neighbor, weight in graph.get(node, []):
            if neighbor not in visited:
                heapq.heappush(heap, (weight, neighbor, node))
    return mst_weight, mst_edges

graph = {0:[(1,1),(2,3)], 1:[(0,1),(2,4),(3,2)], 2:[(0,3),(1,4),(3,5)], 3:[(1,2),(2,5)]}
w, mst = prim(graph)
print(w)    # 6
print(mst)  # [(0, 1, 1), (1, 3, 2), (0, 2, 3)]