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

This page lives under the MST topic (its English parent). We do not re-explain the algorithms — we stress-test them against every awkward input a graph can throw at you: ties, cycles, disconnection, negatives, duplicate edges, single vertices, and a real word problem. If a scenario ever surprises you in an exam, it should be because you saw it here first and know the fix.

Definition Two properties we lean on all page (remember these)

Both come from Cut Property and Cycle Property and are proven in the parent note; we only use them here.

Cut property: split the vertices into two non-empty piles (a cut). The cheapest edge crossing between the piles is safe — it belongs to some MST. This is why both algorithms may greedily grab the lightest crossing edge.
Cycle property: in any cycle, the heaviest edge is never needed — deleting it keeps everything connected for less (or equal) cost. This is why Kruskal skips an edge whose endpoints are already connected.

Notation note: we write $V$ for the number of vertices throughout. In the code snippets from the parent, the variable is named n — read n as "the value of $V$ ". A spanning tree always has exactly $V - 1$ edges.

Definition How to read a Prim heap trace on this page (do not skip)

Prim uses a min-heap (priority queue) whose entries are pairs written $(w, u)$ : the first number $w$ is "the weight of the edge that would let us reach vertex $u$ ", the second number $u$ is the vertex. The heap always pops the pair with the smallest $w$ first — that is what makes it grab the cheapest crossing edge. We track two running quantities as the loop runs:

total — the accumulating MST weight. Every time we pop a fresh (not-yet-visited) vertex, we do total += w for that popped pair, because that $w$ is the edge we are committing to add to the tree. Stale pops (vertex already visited) add nothing.
cnt — a counter of how many vertices we have actually added to the tree (marked visited). It starts at $0$ , and cnt += 1 on every fresh pop. When cnt == V every vertex is in the tree, so we stop. (cnt is the "how many islands are connected so far" number.)

The scenario matrix

Before working examples, let us name every kind of situation MST algorithms must survive. Think of this as a checklist: each row is a "cell", and every example below is tagged with the cell(s) it covers. Nothing is left uncovered.

Cell	Scenario class	The tricky question it forces
C1	Standard connected graph, distinct weights	Do Kruskal and Prim agree? Is the MST unique?
C2	Tied edge weights	MST tree not unique — but is the total unique?
C3	Cycle present (redundant edge)	Which edge gets rejected, and why?
C4	Disconnected graph	No spanning tree exists — how does each algorithm tell us?
C5	Negative edge weights	Does greed still work with values below zero?
C6	Degenerate: single vertex ( $V = 1$ ), or $V = 2$	How many edges? Does the loop even run?
C7	Parallel (duplicate) edges & self-loops	Does the algorithm silently ignore the junk?
C8	Dense vs sparse — which algorithm to choose	Complexity trade-off, real decision
C9	Word problem (islands / cables)	Translate reality → graph → MST
C10	Exam twist: "second-best" / forced edge	Reasoning beyond the plain algorithm

Each cell below is closed by at least one worked example.

Example 1 — Standard graph, both algorithms agree (C1)

Forecast: Guess the total before reading on. Cheapest edges are $1, 2, 2, 3, 4, \dots$ — but two edges weigh $2$ , so a tie is coming. Write down a number.

This is exactly the graph drawn below — orange edges are the ones Kruskal keeps, dashed teal are the ones it will reject. Glance at it now, then follow the steps.

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

Sort edges ascending. $(1, 0, 1), (2, 1, 2), (2, 0, 3), (3, 1, 3), (4, 3, 4), (5, 2, 4), (6, 0, 4)$ . Why this step? Kruskal is greedy over edges — by the cut property the lightest edge crossing between two components is safe, so we must see them cheapest-first.
Add $(1, 0, 1)$ . Sets: ${0, 1}, {2}, {3}, {4}$ . In the figure this is the orange edge $0 - 1$ . Why? $0$ and $1$ are in different components → no cycle → safe.
Add $(2, 1, 2)$ . Sets: ${0, 1, 2}, {3}, {4}$ — orange edge $1 - 2$ . Why? $1$ and $2$ different components.
Add $(2, 0, 3)$ . Sets: ${0, 1, 2, 3}, {4}$ — orange edge $0 - 3$ . Why? $0$ and $3$ different components. (The tie with $(1, 2)$ didn't matter — sort order broke it, and either choice gives the same total; that is cell C2 foreshadowed.)
Skip $(3, 1, 3)$ — the dashed teal edge $1 - 3$ . Why? $1$ and $3$ are already in the same component → adding forms a cycle → cycle property forbids it (this would be the heaviest edge of that cycle).
Add $(4, 3, 4)$ . Sets: ${0, 1, 2, 3, 4}$ — all connected, we now have $V - 1 = 4$ edges → stop. (Edges $(5, 2, 4)$ and $(6, 0, 4)$ stay dashed teal — never examined.) Why stop? A tree on $5$ vertices has exactly $4$ edges; more would create a cycle.

Total $= 1 + 2 + 2 + 4 = 9$ .

Prim from 0 (heap trace, with justifications). Recall the heap pairs are $(w, u)$ , total accumulates, and cnt counts vertices added (both defined in the reading-guide above). Start total = 0, cnt = 0.

Pop $(0, 0)$ — fresh; total += 0 (now $0$ ), cnt += 1 (now $1$ ); mark $0$ visited; push $(1, 1), (2, 3), (6, 4)$ . Why total += 0? We committed to the seed via the artificial pair $(0, 0)$ ; its weight is $0$ because reaching the seed crosses no edge, so it adds nothing. Why the pushes? They are the edges leaving the new frontier ${0}$ , now candidates.
Pop $(1, 1)$ — fresh; total += 1 (now $1$ ), cnt += 1 (now $2$ ); push $(2, 2), (3, 3)$ . Why total += 1? $(1, 1)$ is the cheapest edge crossing the cut $({0}, rest)$ → cut property → safe → we add its weight $1$ to the tree. Vertex $1$ now joins.
Pop $(2, 2)$ — fresh; total += 2 (now $3$ ), cnt += 1 (now $3$ ); push $(5, 4)$ . Why total += 2? Cheapest crossing edge of $({0, 1}, rest)$ is $1 - 2$ at weight $2$ ; committing it adds $2$ .
Pop $(2, 3)$ — fresh; total += 2 (now $5$ ), cnt += 1 (now $4$ ). (This is the $0 - 3$ edge.) Why total += 2? Cheapest crossing edge now is $0 - 3$ at $2$ ; $3$ joins, adding $2$ .
Pop $(4, 4)$ — fresh; total += 4 (now $9$ ), cnt += 1 (now $5$ ). (This is the $3 - 4$ edge.) Why total += 4? Only vertex $4$ remained; its cheapest crossing edge is $3 - 4$ at $4$ . Now cnt == V == 5 → stop.

Total $= 0 + 1 + 2 + 2 + 4 = 9$ . ✅ same.

Recall Did your forecast match?

Both algorithms give 9. If you guessed anything using $(3, 1, 3)$ , you forgot the cycle skip.

Verify: $1 + 2 + 2 + 4 = 9$ ; edge count $= 4 = V - 1$ ; no vertex left unvisited. Checked in VERIFY as ex1_total.

Example 2 — Ties: tree changes, total does not (C2)

Forecast: How many distinct trees connect a triangle? Guess the count.

Any 2 of the 3 edges form a spanning tree. Choosing $2$ from $3$ gives $(2 3) = 3$ trees. Why? $V = 3$ needs $V - 1 = 2$ edges; the third would close the cycle.
All three trees weigh $5 + 5 = 10$ . Why? Every edge is $5$ , so any 2 of them sum to $10$ regardless of which we drop.
Kruskal picks the first two edges the sort happens to list; Prim picks based on heap tie-break. Different runs → different tree, identical total. Why? The cut property only guarantees some MST; with ties, several MSTs exist but share the minimum total.

Verify: number of MSTs $= 3$ , total $= 10$ . Checked as ex2_count, ex2_total.

Example 3 — Cycle rejection in slow motion (C3)

Forecast: The diagonal is heavy ( $10$ ). Guess whether it's ever used.

Sort: four edges of weight $1$ , then $(0, 2, 10)$ . Why? Cheapest first.
Process the weight- $1$ edges in order and add exactly three of them. Adding $(0, 1), (1, 2), (2, 3)$ connects all four vertices with $3 = V - 1$ edges → the tree is complete after three additions. Why? $V = 4 \Rightarrow V - 1 = 3$ edges → tree complete; we stop the instant we reach $3$ .
The fourth weight-1 edge $(3, 0, 1)$ is never added — by the time we would look at it, $3$ and $0$ are already connected, so it would be skipped as a cycle anyway. And $(0, 2, 10)$ is never even examined once we hit $V - 1$ edges. Why? Once the tree has $V - 1$ edges we stop; and the heavy diagonal is exactly the "heaviest edge of a cycle" the cycle property tells us to drop.

Total $= 1 + 1 + 1 = 3$ .

Verify: total $= 3$ ; diagonal weight $10$ unused. Checked as ex3_total.

Example 4 — Disconnected graph: MST does not exist (C4)

Forecast: Can you span $4$ vertices with only $2$ available edges? A spanning tree needs $V - 1 = 3$ .

Kruskal adds $(0, 1, 4)$ and $(2, 3, 7)$ , then runs out of edges with only $2$ added — never reaches $V - 1 = 3$ . Why? There is simply no crossing edge between ${0, 1}$ and ${2, 3}$ to add.
Detection: after the loop, len(mst) < V-1 → the graph is disconnected; report "no spanning tree" (or return a spanning forest of the two components). Why? An MST is only defined for a connected graph.
Prim from 0 grows ${0, 1}$ , then the heap empties (no edge leaves ${0, 1}$ ). The vertex counter cnt stalls at $2 < V = 4$ → same conclusion. Why? Prim can only add crossing edges; with no crossing edge to ${2, 3}$ , the heap empties while cnt is still below $V$ , so it halts early.

Verify: edges collected $= 2$ , required $= 3$ , so is_spanning = False. Checked as ex4_disconnected.

Example 5 — Negative weights are totally fine (C5)

Forecast: Dijkstra breaks on negatives. Do MST algorithms? Guess yes/no.

Sort: $(0, 1, - 3), (1, 2, - 1), (0, 2, 4)$ . Why? MST only ever compares and sorts weights — it never adds a weight to a running distance and relaxes (that is what breaks Dijkstra). So the sign is irrelevant to correctness.
Add $(0, 1, - 3)$ , add $(1, 2, - 1)$ . Now ${0, 1, 2}$ connected with $V - 1 = 2$ edges → stop; $(0, 2, 4)$ skipped. Why? Same greedy rule; negatives just sort to the front.

Total $= - 3 + (- 1) = - 4$ .

Verify: total $= - 4$ . Checked as ex5_total.

Example 6 — Degenerate sizes: $V = 1$ and $V = 2$ (C6)

Forecast: How many edges does a $1$ -vertex tree have? A $2$ -vertex tree?

Case (a), $V = 1$ : MST edges $= V - 1 = 0$ . Total $= 0$ . Why? A single vertex is already a valid (trivial) spanning tree — nothing to connect. Kruskal's loop finds len(mst)==0==V-1 immediately; Prim pops the seed pair $(0, 0)$ , does total += 0, cnt += 1 making cnt == 1 == V, and stops.
Case (b), $V = 2$ : MST edges $= V - 1 = 1$ . Must take the only edge → total $= 8$ . Why? One edge is both necessary (to connect) and sufficient (a tree).

Verify: (a) total $= 0$ , edges $= 0$ ; (b) total $= 8$ , edges $= 1$ . Checked as ex6a, ex6b.

Example 7 — Parallel edges and self-loops, in BOTH algorithms (C7)

Forecast: Which of the two parallel $0 - 1$ edges survives? Does the self-loop ever help?

Kruskal:

Self-loop $(0, 0, 1)$ is discarded immediately: its endpoints are the same vertex → find(0)==find(0) → cycle of length 0. Why? A self-loop can never cross any cut; it connects nothing new.
Of the parallel edges, sort puts $(0, 1, 2)$ before $(0, 1, 9)$ . Add $(0, 1, 2)$ ; then $(0, 1, 9)$ is skipped (already same component → cycle property). Why? The cheaper parallel edge wins; the expensive twin is a cycle edge.
Add $(1, 2, 3)$ . Now $3$ vertices, $2$ edges $= V - 1$ → stop.

Kruskal total $= 2 + 3 = 5$ .

Prim from 0 (heap trace). Recall pairs are $(w, u)$ ; total accumulates on fresh pops, cnt counts vertices added. Start total = 0, cnt = 0.

Pop $(0, 0)$ — fresh; total += 0 (now $0$ ), cnt += 1 (now $1$ ); mark $0$ visited. Push its outgoing edges: the self-loop $(0, 0, 1)$ pushes the pair $(1, 0)$ — an entry claiming to reach vertex $0$ at cost $1$ — plus both parallel edges push $(9, 1)$ and $(2, 1)$ . Why push all of them? The lazy heap does not pre-filter; it pushes every incident edge and sorts out staleness later, on pop.
Pop $(1, 0)$ — the self-loop's entry — vertex $0$ already visited → stale → continue (no total +=, no cnt +=). Why no accumulation? A stale pop commits no edge, so total and cnt are untouched. This is exactly how Prim ignores a self-loop: its entry pops stale and is discarded by if visited[u]: continue.
Pop $(2, 1)$ — fresh (cheaper parallel edge); total += 2 (now $2$ ), cnt += 1 (now $2$ ); mark $1$ visited. Push $(3, 2)$ . Why total += 2? $(2, 1)$ is the min-heap's smallest pair, i.e. the cheapest crossing edge of $({0}, rest)$ ; committing it adds weight $2$ . It pops before $(9, 1)$ because $2 < 9$ .
Later the stale $(9, 1)$ pops — vertex $1$ already visited → continue (no total +=). Why no accumulation? Same lazy-deletion trick: this is how Prim ignores the duplicate/parallel edge — the expensive twin is a stale pop that never adds weight.
Pop $(3, 2)$ — fresh; total += 3 (now $5$ ), cnt += 1 (now $3$ ). Now cnt == V == 3 → stop.

Prim total $= 0 + 2 + 3 = 5$ . ✅ same as Kruskal.

Verify: total $= 5$ (both algorithms); self-loop and the $9$ -edge both unused. Checked as ex7_total.

Example 8 — Which algorithm? Sparse vs dense (C8)

Forecast: Guess "Kruskal for A, Prim for B" — then justify with numbers.

Kruskal costs $O (E lo g E)$ , dominated by sorting edges. Graph A: $\approx 1.2 \times 1 0^{5} \times lo g_{2} (1.2 \times 1 0^{5}) \approx 1.2 \times 1 0^{5} \times 17 \approx 2.0 \times 1 0^{6}$ ops. Why? Sparse graphs have an edge list already; sorting few edges is cheap.
Prim (binary heap) costs $O (E lo g V)$ . Graph B: $\approx 2 \times 1 0^{6} \times lo g_{2} (2000) \approx 2 \times 1 0^{6} \times 11 \approx 2.2 \times 1 0^{7}$ ops. Kruskal on B would sort $2 \times 1 0^{6}$ edges: $2 \times 1 0^{6} \times lo g_{2} (2 \times 1 0^{6}) \approx 2 \times 1 0^{6} \times 21 \approx 4.2 \times 1 0^{7}$ — nearly double. Why? $lo g V < lo g E$ when $E ≫ V$ (dense), so Prim's $lo g V$ factor wins.
Decision: sparse/edge-list → Kruskal; dense/adjacency-list → Prim. Why this decision? When $E$ is small (sparse), the sort in Kruskal is cheap and you often already hold an edge list, so $O (E lo g E)$ is minimal work. When $E$ is huge (dense, $E \approx V^{2}$ ), $lo g E \approx 2 lo g V$ , so Prim's $O (E lo g V)$ strictly beats Kruskal's $O (E lo g E)$ — and Prim reads the adjacency list you'd naturally store for a dense graph. Match the algorithm to the data structure you already have.

Verify: the four op-count estimates are checked (order-of-magnitude) as ex8_ops.

Example 9 — Word problem: island cables (C9)

Forecast: Guess the total in ₹ crore before solving.

Model: islands → vertices, cables → weighted undirected edges. "Every island reachable, least cost, no wasted loop" = MST. Why? Connectivity + minimum total weight + no cycle is precisely the MST definition.
Kruskal, sorted: $B - C (1), A - B (2), A - C (3), B - D (4), C - E (5), D - E (6)$ . Process each with a Why:
- Add $B - C$ (1): ${B, C}$ . Why? $B, C$ different components → lightest crossing edge → safe (cut property).
- Add $A - B$ (2): ${A, B, C}$ . Why? $A$ is in its own component; joining it costs no cycle.
- Skip $A - C$ (3): Why? $A$ and $C$ are already in the same component → would form a cycle → cycle property rejects it (heaviest edge of that triangle).
- Add $B - D$ (4): ${A, B, C, D}$ . Why? $D$ is a new component; cheapest edge reaching it is $B - D$ .
- Add $C - E$ (5): all $5$ connected, $4 = V - 1$ edges → stop. Why? $E$ is the last isolated island; $C - E$ at $5$ is the cheapest cable reaching it (cheaper than $D - E$ at $6$ ).
- Skip $D - E$ (6): Why? We already have $V - 1$ edges; it would add a cycle and is more expensive anyway.
Cables built: $B - C, A - B, B - D, C - E$ .

Total $= 1 + 2 + 4 + 5 = 12$ ₹ crore.

Recall Units sanity check

Weights are ₹ crore, we only added them (never multiplied), so the answer is in ₹ crore. $4$ cables connect $5$ islands — correct ( $V - 1$ ).

Verify: total $= 12$ , edge count $= 4$ . Checked as ex9_total.

Example 10 — Exam twist: forced-edge / second-best (C10)

Forecast: More or less than the free MST ( $12$ )? Guess.

Contract the forced edge first: put $D - E$ (cost $6$ ) into the tree, then run MST on the rest treating $D, E$ as already connected. Why? A forced edge = "pretend its endpoints are pre-merged", then let greed handle the remaining cut.
Build DSU with $D, E$ pre-unioned, then Kruskal over the rest sorted $B - C (1), A - B (2), A - C (3), B - D (4), C - E (5)$ . Process with a Why each:
- Add $B - C (1)$ : ${B, C}$ . Why? Different components → safe.
- Add $A - B (2)$ : ${A, B, C}$ . Why? $A$ new → safe.
- Skip $A - C (3)$ : Why? $A, C$ already connected → cycle.
- Add $B - D (4)$ : now ${A, B, C}$ merges with the pre-connected ${D, E}$ → all five joined. Why? $B$ 's component and $D$ 's (= $E$ 's) component were still separate.
- Stop: we now have $D - E$ plus three added edges $= 4 = V - 1$ . Skip $C - E (5)$ — it would form a cycle now that $E$ is reachable, and we already hit $V - 1$ edges.
Edges: $D - E (6), B - C (1), A - B (2), B - D (4)$ .

Total $= 6 + 1 + 2 + 4 = 13$ ₹ crore — exactly 1 more than the free optimum, the price of the forced cable (we replaced $C - E$ at $5$ with $D - E$ at $6$ ).

Verify: forced total $= 13 = 12 + 1$ . Checked as ex10_total.

Coverage check

Recall Every cell closed?

C1 → Ex1 · C2 → Ex2 · C3 → Ex3 · C4 → Ex4 · C5 → Ex5 · C6 → Ex6 · C7 → Ex7 · C8 → Ex8 · C9 → Ex9 · C10 → Ex10. Full matrix covered.

Which cell tests disconnection?

C4 — Example 4, where the collected edge count stays below

V - 1

, signalling no spanning tree.

Do negative weights break MST greed?

No — MST only compares/sorts weights (Example 5), unlike Dijkstra which relaxes along paths.

With tied weights, what is guaranteed unique?

The total MST weight, not the specific tree (Example 2).

How do you enforce a forced edge in an MST?

Pre-union its endpoints (contract it), then run Kruskal on the rest (Example 10).

How does Prim ignore a self-loop or parallel edge?

The stale heap entry pops when the vertex is already visited and is skipped by if visited[u]: continue, so it never runs total += (Example 7).

In a Prim heap pair, what does each of the two numbers mean?

The first is the edge weight

w

to reach the vertex; the second is the vertex

u

— the heap pops smallest

w

first.

What is cnt in the Prim trace?

A counter of vertices already added to the tree; it hits

V

exactly when the MST is complete.

Connections

Disjoint Set Union (Union-Find) — silently rejects self-loops and parallel edges (Ex7).
Priority Queue (Binary Heap) — Prim's frontier; heap tie-break explains Ex2.
Cut Property and Cycle Property — the two properties defined at the top and used every example.
Dijkstra's Algorithm — contrast in Ex5: it does break on negatives.
Greedy Algorithms — the exchange argument reused in Ex10.
Graph Representations — edge list (Kruskal) vs adjacency list (Prim).