Minimum Spanning Tree — Kruskal's (Union-Find), Prim's (priority queue): Visual walkthrough

We assume nothing. If a word appears, we draw it first.

Step 1 — What is a graph, a weight, and a tree? (drawing our vocabulary)

WHAT. A graph is a set of dots (vertices) joined by lines (edges). Each edge carries a number, its weight — think "cost of building this bridge." We only ever deal with undirected edges: a line from $u$ to $v$ is the same as from $v$ to $u$ (a bridge you can cross both ways).

WHY. Before we can say "cheapest total," we must fix what "total" means. The total cost of a set of edges is just the sum of their weights.

PICTURE. Four islands, five possible bridges with their prices painted on.

Figure — Minimum Spanning Tree — Kruskal's (Union-Find), Prim's (priority queue)

Here $V = 4$ , so any spanning tree uses $V - 1 = 3$ bridges. The Minimum Spanning Tree (MST) is the cheapest such choice.

Step 2 — Why cycles are always wasteful (the seed of greed)

WHAT. Suppose your chosen edges contain a cycle — a closed loop $v_{1} \to v_{2} \to \dots \to v_{1}$ .

WHY. Look at the heaviest edge on that loop. Delete it. Everything the loop connected is still connected — because the rest of the loop is another path around. So we dropped weight for free.

$cost after removal = cost before - heaviest loop edge, > 0 or \geq 0 w_{m a x} \leq cost before$

Every symbol: $w_{m a x}$ is the largest weight on the cycle; removing it can only lower (or tie) the total. So a cheapest connected structure never keeps a cycle — it is a tree.

PICTURE. A triangle-loop with the heaviest edge highlighted, then erased — connectivity survives.

Step 3 — Draw a "cut" and define a crossing edge

WHAT. A cut is any way to split the vertices into two non-empty piles $S$ and $V ∖ S$ (read " $V$ minus $S$ " — everything not in $S$ ). Picture a wall drawn through the graph. An edge is a crossing edge if one end sits in $S$ and the other in $V ∖ S$ — it pokes through the wall.

WHY. A spanning tree must connect the two piles somehow, so at least one crossing edge must be in the tree. The whole question becomes: which crossing edge?

PICTURE. The wall splits ${0, 1}$ from ${2, 3}$ . Crossing edges glow; internal edges are dim.

$S = {0, 1}, V ∖ S = {2, 3}$

$S$ :: the pile we've drawn on the left of the wall.
$V ∖ S$ :: everyone else — the right pile.
crossing edges here :: $(1, 2, 2)$ , $(0, 2, 3)$ , $(2, 3, 4)$ , $(0, 3, 5)$ — each has one endpoint on each side.

The cheapest crossing edge is $(1, 2)$ with weight $2$ . Claim: it is safe to use. Step 4 proves it.

Step 4 — The Cut Property, proved by a swap you can see

WHAT. Let $e = (u, v)$ be the lightest crossing edge of some cut. Claim: some MST contains $e$ .

WHY (the exchange argument). Suppose an MST $T$ does not contain $e$ . Add $e$ to $T$ . A tree plus one extra edge makes exactly one cycle (Step 1's picture, in reverse). Follow that cycle: it starts in $S$ , ends back in $S$ , so it must cross the wall an even number of times — meaning there is another crossing edge $f$ on the cycle.

$w (e) \leq w (f) because e is the lightest crossing edge$

Now swap: remove $f$ , keep $e$ .

$T^{'} = T - f + e, w (T^{'}) = w (T) - w (f) + w (e) \leq w (T)$

Reading it term by term: we paid $w (e)$ , refunded $w (f)$ , and since $w (e) \leq w (f)$ the net change is $\leq 0$ . $T^{'}$ is still a spanning tree (we broke the cycle, kept everything connected). So an MST containing $e$ exists. $■$

PICTURE. $T$ in mint, the added edge $e$ in coral forming a loop, the other crossing edge $f$ in lavender getting deleted.

This is a proof by exchange, the classic pattern of Greedy Algorithms.

Step 5 — Kruskal is "move the wall to wherever the next cheap edge is"

WHAT. Sort all edges cheapest-first. Walk the list; add an edge if its two endpoints are in different components; skip it otherwise.

WHY it's just the cut property. When you meet the cheapest edge $(u, v)$ whose endpoints are still in different components, put $u$ 's whole component on one side of an imaginary wall and everyone else on the other. Every crossing edge cheaper than $(u, v)$ was already processed and couldn't connect these two groups (or they'd already be one component). So $(u, v)$ is the lightest crossing edge of that cut → safe.

Skipping happens when both endpoints are already the same component — adding the edge would close a cycle (Step 2 says: useless).

PICTURE. Edges laid out sorted; we sweep left→right, accept (mint) or reject-as-cycle (coral), and watch components merge.

Step	Edge	Same component?	Action
1	$(0, 1, 1)$	no	add
2	$(1, 2, 2)$	no	add
3	$(0, 2, 3)$	yes ( $0, 2$ linked via $1$ )	skip — cycle
4	$(2, 3, 4)$	no	add → 3 edges = $V - 1$ → stop

MST weight $= 1 + 2 + 4 = 7$ .

The "same component?" test must be fast — that engine is Disjoint Set Union (Union-Find).

Step 6 — Prim is "keep the wall around one growing blob"

WHAT. Start with one seed vertex as your set $S$ . Repeatedly add the cheapest crossing edge of the cut $(S, V ∖ S)$ , absorbing the new vertex into $S$ . Repeat until $S = V$ .

WHY it's just the cut property. Here the cut is explicit and literally the growing tree: at every step the edge we pick is by construction the min crossing edge of $(S, V ∖ S)$ — safe, directly.

HOW fast. To always grab the globally cheapest crossing edge, keep candidate edges in a min-Priority Queue (Binary Heap). Pop the smallest; if it leads to an already-visited vertex, it's stale — just skip it (lazy deletion).

PICTURE. The blob $S$ grows from vertex $0$ ; the frontier edges live in a heap; the smallest one is pulled in each round.

Prim from $0$ : pop $0$ → frontier ${(1, 1), (3, 2), (5, 3)}$ → pop $(1, 1)$ , add $1$ → push $(2, 2)$ → pop $(2, 2)$ , add $2$ → push $(4, 3)$ → pop $(4, 3)$ , add $3$ .

$total = 0 + 1 + 2 + 4 = 7$

Same $7$ as Kruskal — because both obey the cut property, and the MST weight is unique (even when the tree itself isn't). This heap skeleton is shared with Dijkstra's Algorithm; the only difference is Prim's key is edge weight, Dijkstra's is distance from source.

Step 7 — Edge and degenerate cases (never leave the reader stranded)

WHAT / WHY, case by case:

Ties (equal weights). The cut property says "some MST." With ties there may be several MSTs, all of equal total weight. Kruskal's tie-break order just picks one of them — still correct.
Disconnected graph. No spanning tree exists at all. Kruskal ends with fewer than $V - 1$ edges (it never merges into one component); Prim's heap empties before $S = V$ . You get a Minimum Spanning Forest, one tree per connected piece.
Single vertex ( $V = 1$ ). $V - 1 = 0$ edges. Both algorithms do nothing and return weight $0$ . Not a bug — a tree on one vertex is that vertex.
Negative weights. Totally fine. MST algorithms only compare and sort weights; they never add weights along a path the way Dijkstra does, so no negative-weight trap exists.
Self-loop $(u, u)$ . Both endpoints are the same component instantly → always skipped.
Parallel edges (two bridges between the same pair). The cheaper one may be used; the dearer one is the heavier edge of a 2-cycle → dropped by Step 2.

PICTURE. Four mini-panels: a tie, a disconnected graph (→ forest), a lone vertex, and a negative-weight edge that still gets chosen.

The one-picture summary

Everything above collapses to one loop: find a wall, cross it as cheaply as possible, absorb the new side, repeat. Kruskal picks the wall implicitly (wherever the next cheap edge lands); Prim keeps one wall wrapped around a growing blob. Same theorem, same weight, two costumes.

Recall Feynman retelling — the whole walkthrough in plain words

You have islands and priced bridges, and you want everyone connected for the least money. First truth: any loop of bridges wastes cash, because you can always burn the priciest bridge in the loop and still walk everywhere — so the answer never has loops (it's a tree). Second truth: draw a wall anywhere splitting the islands into two groups. Somebody has to cross it, so pick the cheapest bridge that crosses — that choice can never be a mistake (if a "better" answer skipped it, you could swap it in and pay no more). That single move is the whole game. Kruskal plays it by sorting every bridge cheapest-first and building each one unless it just loops back into a group you already joined. Prim plays it by starting on one island and always extending with the cheapest bridge that reaches somewhere new. Different order of moves, identical minimum bill.

Recall

Why is the heaviest edge of a cycle safe to delete? ::: Its endpoints stay connected through the rest of the cycle, and the total weight drops — so a cheapest connected graph never keeps it. In the cut property proof, what forces another crossing edge $f$ to exist? ::: Adding $e$ makes one cycle; the cycle leaves and returns to $S$ , so it crosses the wall an even (≥2) number of times. Why do Kruskal and Prim give the same total? ::: Both only ever add lightest crossing edges (cut property), and the MST weight is unique even when the tree isn't. What happens on a disconnected graph? ::: No spanning tree exists; you get a minimum spanning forest — fewer than $V - 1$ edges.

Connections

Cut Property and Cycle Property — the theorem Steps 2–4 build from scratch.
Disjoint Set Union (Union-Find) — the fast "same component?" test in Kruskal (Step 5).
Priority Queue (Binary Heap) — the cheapest-frontier engine in Prim (Step 6).
Greedy Algorithms — the exchange-argument proof pattern of Step 4.
Dijkstra's Algorithm — same heap loop as Prim, different key.
Graph Representations — edge list (Kruskal) vs adjacency list (Prim).