Minimum Spanning Tree

Cheapest way to connect everything

A Minimum Spanning Tree (MST) connects all V nodes using exactly V-1 edges with the smallest total weight, and no cycles. Think: laying cable to connect cities at minimum cost.

Kruskal's — sort edges, union-find

Sort all edges by weight. Add an edge if its two endpoints are in different components (checked via Union-Find), which avoids cycles.

def kruskal(n, edges):
    parent = list(range(n))

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

    mst_weight, count = 0, 0
    for w, u, v in sorted(edges):        # edges as (weight, u, v)
        ru, rv = find(u), find(v)
        if ru != rv:
            parent[ru] = rv
            mst_weight += w
            count += 1
            if count == n - 1:
                break
    return mst_weight

Prim's — grow from a node

Start from any node and repeatedly add the cheapest edge leaving the current tree to a new node, using a min-heap — similar shape to Dijkstra.

import heapq

def prim(n, g, start=0):
    visited = [False] * n
    pq = [(0, start)]
    total = 0
    while pq:
        w, u = heapq.heappop(pq)
        if visited[u]:
            continue
        visited[u] = True
        total += w
        for v, wt in g[u]:
            if not visited[v]:
                heapq.heappush(pq, (wt, v))
    return total

Kruskal vs Prim

Kruskal's, O(E log E), shines on sparse graphs since it works edge-by-edge. Prim's, O(E log V) with a heap, shines on dense graphs since it grows one tree node-by-node.