MST — cheapest connection of all nodes

Spanning tree = subset of edges connecting all V nodes, no cycles, V-1 edges. Minimum spanning tree minimizes total edge weight. Two clean approaches: Kruskal (greedy on edges + DSU) and Prim (greedy from a node + heap).

The vocabulary, defined once

Every term you need lives in one place so you never have to look elsewhere. Read these slowly; the rest of the lesson leans on them.

• Graph. A set of nodes (also called vertices — the towns) joined by edges (the roads). We write V for the number of nodes and E for the number of edges.
• Weighted undirected graph. "Weighted" means each edge carries a number (its cost, length, or weight). "Undirected" means an edge between u and v can be travelled both ways — a two-way road, not a one-way street. MST is only defined on weighted undirected graphs; if the edges had directions you would be solving a different (harder) problem called the arborescence.
• Cycle. A path that leaves a node and returns to it without reusing an edge — a closed loop. Any extra edge added to a tree creates exactly one cycle, which is why MSTs never contain cycles: a cycle always has one edge you could drop while staying connected, so keeping it just wastes weight.
• Spanning tree. A subset of the edges that touches (spans) all V nodes, keeps the whole thing connected, and contains no cycle. Such a subset always has exactly V−1 edges. Fewer than V−1 → some node is cut off (disconnected); more than V−1 → you have introduced a cycle.
• Minimum spanning tree (MST). Among all possible spanning trees, the one whose edge weights add up to the smallest total. (If two edges tie in weight there can be several different MSTs, but they all share the same minimum total.)
• Greedy. A strategy that, at each step, grabs the locally best-looking option (here: the cheapest legal edge) and never undoes a choice. Greedy does not always work — but for MST it provably does, thanks to the cut property below.
• Cut property. Cut the nodes into any two non-empty groups. The single lightest edge that crosses between the groups is safe to put in an MST. This one fact is the engine: it is why repeatedly taking a cheapest "crossing" edge is guaranteed optimal.

Kruskal's algorithm, step by step

Kruskal's algorithm ignores where nodes sit and works purely on the list of edges. The recipe is three lines of intent: (1) sort every edge cheapest-first; (2) walk the sorted list and add each edge only if its two endpoints are not already connected; (3) stop once you have added V−1 edges. The "are they already connected?" question is answered by union-find (DSU), described just below. Here is the same trace from the walkthrough laid out as a table you can replay by hand on the edge list (1,0,1), (2,1,2), (2,2,3), (3,0,2), (4,0,3):

# Sorted edges (weight, u, v):  (1,0,1) (2,1,2) (2,2,3) (3,0,2) (4,0,3)
# groups start as singletons:   {0} {1} {2} {3}

# (1,0,1): 0 and 1 in different groups -> KEEP. groups: {0,1} {2} {3}   total=1 picked=1
# (2,1,2): 1 and 2 in different groups -> KEEP. groups: {0,1,2} {3}     total=3 picked=2
# (2,2,3): 2 and 3 in different groups -> KEEP. groups: {0,1,2,3}       total=5 picked=3 == V-1 -> STOP
# (3,0,2): 0 and 2 ALREADY same group  -> would form a cycle -> SKIP  (never reached, we stopped)
# (4,0,3): 0 and 3 ALREADY same group  -> would form a cycle -> SKIP  (never reached, we stopped)
# MST total = 1 + 2 + 2 = 5, using V-1 = 3 edges.

The discipline is simple: take the cheapest edge available; if it bridges two separate pieces, it must be part of a cheapest connection (cut property), so keep it; if both ends are already in one piece, it can only add a cycle, so throw it away. Repeat until everything is one piece.

def kruskal(n, edges):
    # edges: list of (weight, u, v)
    edges.sort()
    dsu = DSU(n)
    total = 0; picked = 0
    for w, u, v in edges:
        if dsu.union(u, v):     # returns True if joined two different components
            total += w; picked += 1
            if picked == n - 1: break
    return total if picked == n - 1 else -1   # -1 = graph disconnected

Union-find (DSU): the cycle detector

Kruskal needs to answer one question over and over: "are nodes u and v already in the same connected piece?" Union-find (a.k.a. Disjoint Set Union, DSU) is the data structure that answers it almost instantly. It keeps each group as a tree of parent pointers, with one representative "root" per group. Two operations: find(x) climbs to x's root (the group's id), and union(u, v) joins two groups by pointing one root at the other.

class DSU:
    def __init__(self, n):
        self.parent = list(range(n))   # each node starts as its own group/root
        self.rank = [0] * n           # tree height hint, keeps trees flat
    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])  # path compression: flatten on the way up
        return self.parent[x]
    def union(self, a, b):
        ra, rb = self.find(a), self.find(b)
        if ra == rb: return False     # already same group -> adding edge makes a CYCLE
        if self.rank[ra] < self.rank[rb]: ra, rb = rb, ra  # attach smaller under larger
        self.parent[rb] = ra
        if self.rank[ra] == self.rank[rb]: self.rank[ra] += 1
        return True                  # genuinely merged two groups

With both optimizations — path compression (flatten the chain during find) and union by rank (always hang the shorter tree under the taller one) — each operation costs amortized α(n), the inverse-Ackermann function, which is below 5 for any input that fits in the universe. Treat it as a constant. That is why the only term that matters in Kruskal's cost is the initial sort.

Prim's algorithm: grow one tree from a seed

Prim's algorithm takes the opposite stance from Kruskal. Instead of scanning a global sorted edge list, it starts from one arbitrary node and grows a single connected tree outward, always reaching for the cheapest edge that leaves the tree and lands on a node not yet inside it. To always find that cheapest frontier edge fast, it uses a priority queue (a min-heap): a structure that hands back the smallest item in O(log n). Tracing the same graph from seed node 0: the tree {0} sees edge (1) to node 1 — take it, tree {0,1}; the frontier now offers (2) to node 2 — take it, tree {0,1,2}; the frontier offers (2) to node 3 — take it, tree {0,1,2,3} is complete. Same total, 5; same three edges. Kruskal sorts all edges once; Prim repeatedly pops the heap, lazily ignoring edges whose target is already absorbed.

import heapq

def prim(graph, n):
    seen = [False] * n
    pq = [(0, 0)]              # (weight, node)
    total = 0; picked = 0
    while pq and picked < n:
        w, u = heapq.heappop(pq)
        if seen[u]: continue
        seen[u] = True; total += w; picked += 1
        for v, ew in graph[u]:
            if not seen[v]:
                heapq.heappush(pq, (ew, v))
    return total if picked == n else -1

Complexity, and which to pick

Both are greedy and both produce a correct MST; the difference is bookkeeping and therefore cost. Read "sparse" as "few edges, E close to V" (a road map) and "dense" as "many edges, E close to V²" (everything wired to everything).

Rule of thumb: if you are handed an edge list and the graph is sparse, reach for Kruskal (it is the shorter interview answer). If you are handed an adjacency list and the graph is dense, reach for Prim. Either is acceptable for most problems; pick the one that matches the input format you were given.

Compute MST total weight with Kruskal and union-find: