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

WHAT: A spanning tree touches every vertex and contains no cycle. WHY that count: A tree on $V$ vertices always has exactly $V-1$ edges — the very first edge joins $2$ vertices into one group, and every later edge must join one new vertex to the existing group (if it joined two already-connected vertices it would form a cycle). So each of the remaining $V-1$ vertices contributes exactly one edge. Here $V=5$, so the MST has $\boxed{V-1=4}$ edges.

find(x) answers "which group (root) does vertex $x$ belong to right now?" by walking parent pointers up to the representative. union(a,b) returning False means "$a$ and $b$ were already in the same group" — merging them would create a cycle, so Kruskal must reject that edge. See Disjoint Set Union (Union-Find).

True. Take any cut that separates the two endpoints of that cheapest edge (for example, one endpoint alone on side $S$). The cheapest edge in the whole graph is certainly the cheapest edge crossing that cut. By the cut property, the minimum-weight crossing edge is safe → it belongs to some MST. In our graph that edge is $(0,1,1)$.

WHAT we do: sort edges ascending, then add each if it joins two different components. Sorted edges: $(0,1,1),(1,2,2),(2,3,3),(0,2,4),(2,4,5),(3,4,6),(1,3,7)$.

MST edges: $(0,1),(1,2),(2,3),(2,4)$. Total $=1+2+3+5=\boxed{11}$. See the highlighted tree:

WHAT: grow a tree $S$ from $\{0\}$, always popping the cheapest frontier edge; skip pops to already-visited vertices. Start: heap $=\{(0,0)\}$.

Total $=0+1+2+3+5=\boxed{11}$. Same as Kruskal — as it must be, since MST weight is unique. See Priority Queue (Binary Heap) for the heap machinery.

Start $p=[0,1,2,3,4]$, rank all $0$.

• union(0,1): equal ranks → attach $1$ under $0$, r[0]=1. $p=[0,0,2,3,4]$.
• union(1,2): find(1)=0 (rank 1), find(2)=2 (rank 0) → attach $2$ under $0$. $p=[0,0,0,3,4]$.
• union(2,3): find(2)=0 (rank 1), find(3)=3 (rank 0) → attach $3$ under $0$. $p=[0,0,0,0,4]$.

Final parents: $p=[0,0,0,0,4]$. Roots: $\text{find}(0)=\text{find}(1)=\text{find}(2)=\text{find}(3)=0$, and $\text{find}(4)=4$. So components are $\{0,1,2,3\}$ and $\{4\}$ — matching the table in 2.1.

WHAT changes: vertex $4$ was reached cheapest through $(2,4,5)$. Now that edge costs $8$. The other edge into $4$ is $(3,4,6)$. Re-sort the relevant tail: $(0,1,1),(1,2,2),(2,3,3),(0,2,4),(3,4,6),(1,3,7),(2,4,8)$. Kruskal adds $(0,1),(1,2),(2,3)$, skips $(0,2)$ (cycle), then adds $(3,4,6)$ — that gives $4$ edges, stop. New MST weight $=1+2+3+6=\boxed{12}$. The tree changed: the edge into $4$ is now $(3,4)$ instead of $(2,4)$.

Claim: with all-distinct weights the MST is unique. Why (cut argument): For every cut, the minimum crossing edge is now strictly smallest, so it is forced — there is no tie to break differently. The cut property then says this exact edge is in the MST. Since every safe edge is uniquely determined by the cuts, no two different spanning trees can both be minimal. This is the cut/cycle property pushed to its strict form. (With ties, several MSTs can share the same minimum weight — as we saw comparing Kruskal and Prim.)

Kruskal: the dominating step is sorting all $E$ edges → $O(E\log E)$. The Union-Find work over $E$ edges is only $O(E\alpha (V))$, essentially linear, so it doesn't dominate. Prim (binary heap): we do at most $O(E)$ pushes and pops, each $O(\log (\text{heap size}))$. The heap holds at most $O(E)$ entries in the lazy version, but with an indexed/decrease-key heap it holds at most $V$ entries → each op $O(\log V)$, total $O(E\log V)$. Note $\log E\le \log V^2=2\log V=O(\log V)$, so the two bounds are the same order — but on dense graphs ($E\approx V^2$) the vertex-based heap is the tighter description. Compare with Dijkstra's Algorithm, which shares Prim's heap skeleton.

($\Leftarrow$) Suppose $e$ is the strictly heaviest edge on some cycle $C$. If any MST $T$ contained $e$, deleting $e$ splits $T$ into two components; some other edge $f$ of $C$ crosses that split (a cycle re-connects). Since $e$ was strictly heaviest, $w(f)<w(e)$, so $T-e+f$ is a spanning tree of smaller weight — contradiction. Hence $e$ is in no MST. ($\Rightarrow$) If $e$ is in no MST, then adding $e$ to any MST creates a cycle where $e$ is the heaviest (otherwise the swap argument would let $e$ replace a heavier edge and improve the MST, forcing $e$ into an MST). Apply: cycle $0-1-2-0$ has weights $1,2,4$. Edge $(0,2,4)$ is strictly heaviest → it is in no MST, exactly why Kruskal skipped it in 2.1. This mirrors the greedy exchange argument of Greedy Algorithms.

Algorithm:

1. Create a fresh DSU on $V$ vertices.
2. For each edge in $T$: if union(u,v) returns False, there is a cycle → reject.
3. After all edges, if we accepted exactly $V-1$ edges and every vertex shares one root → it is a spanning tree.

Union-Find gives near-constant per operation, so total $O(E\alpha (V))$. Verify for $\{(0,1),(1,2),(2,3),(2,4)\}$ on $V=5$:

• union(0,1)✓, union(1,2)✓, union(2,3)✓, union(2,4)✓ — all True, 4 unions, no cycle.
• All five vertices end with the same root → connected. ✅ It is a spanning tree (and indeed the MST from 2.1).

WHAT: the starting seed changes the order of growth but not the final MST weight — every step still picks a minimum crossing edge, all justified by the cut property. Start $S=\{4\}$, heap $\{(0,4)\}$:

• pop $(0,4)$ → visit $4$, push $(5,2),(6,3)$
• pop $(5,2)$ → visit $2$, push $(4,0),(2,1),(3,3)$
• pop $(2,1)$ → visit $1$, push $(1,0),(7,3)$
• pop $(1,0)$ → visit $0$
• pop $(3,3)$ → visit $3$; all visited, stop

Total $=0+5+2+1+3=\boxed{11}$. Same weight, different growth order — as required.

New sorted edges: $(0,1,1),(1,2,2),(4,5,2),(2,3,3),(0,2,4),(2,4,5),(3,4,6),(1,3,7),(1,5,10)$. Now $V=6$, so MST needs $5$ edges. Kruskal:

• $(0,1,1)$ add
• $(1,2,2)$ add
• $(4,5,2)$ add — joins $\{4\}$ and $\{5\}$
• $(2,3,3)$ add
• $(0,2,4)$ skip (cycle $0-1-2$)
• $(2,4,5)$ add — joins group $\{0,1,2,3\}$ with group $\{4,5\}$ → now $5$ edges, stop

MST weight $=1+2+2+3+5=\boxed{13}$. Vertex $5$ attaches through $(4,5,2)$ — the only cheap bridge into the isolated pair $\{4,5\}$, forced by the cut $(\{4,5\},\text{rest})$ whose cheapest crossing edge is $(2,4,5)$.

Proof: Both Kruskal and Prim only ever compare weights ($a<b$) — never add along paths in a way that mixes scales. For $c>0$, $a<b⟺ca<cb$, so every comparison outcome is unchanged → the algorithm makes the identical accept/reject decisions → identical edge set. The total is a sum of the chosen weights, each multiplied by $c$, so the total also multiplies by $c$. Apply: original MST total $=11$, so with $c=3$ the new total $=3\times 11=\boxed{33}$, same edges $(0,1),(1,2),(2,3),(2,4)$. (Note: this fails for $c<0$ or non-monotone transforms, since comparisons flip.)

WHAT each does at every step: Prim's cut is explicit — $(S,V\setminus S)$ with $S$ the grown tree; it picks the minimum crossing edge → safe by cut property. Kruskal's cut is implicit — when it accepts edge $(u,v)$, $u$ and $v$ lie in two separate components; consider the cut with one of those components as $S$; the accepted edge is the cheapest edge crossing that cut among remaining edges, and no cheaper crossing edge was rejected (rejected edges only ever formed cycles inside a component, never crossing this cut). So Kruskal too always adds a safe minimum crossing edge. WHY totals match: Every step of both algorithms adds only safe edges, and both build a full spanning tree. A spanning tree assembled entirely from cut-property-safe edges achieves the minimum possible total (this is the exchange-argument optimum). Two minimum totals over the same graph must be equal — even if the edge sets differ when weights tie. Confirm on $G$: Kruskal total $=11$ (2.1), Prim-from-0 total $=11$ (2.2), Prim-from-4 total $=11$ (4.3). All equal. ∎

Why does Kruskal skip edge $(0,2,4)$ but keep $(2,3,3)$? ::: $(0,2)$ closes cycle $0-1-2$ where it is the heaviest edge (cycle property → in no MST); $(2,3)$ joins two separate components and is the cheapest crossing edge of that cut (cut property → safe).