Spanning Tree: 19-Soft-A1 Algorithms & Data Structures, May 2013, Q4

Question 4: Spanning Tree (10 marks: 2, 5, 3)

Question text not reproduced: the examination questions are © Engineers and Geoscientists BC. Open the official past paper (linked at the top of this page) to read the question, then follow the worked solution below.

Given. $V=\{a,b,c,d,e,f,g,h\}$ (8 vertices) and the 12 weighted edges listed above. Find. a spanning tree of $G$ of minimum total edge weight.

1. The graph — 2 marks

Figure 2 — The undirected weighted graph $G$, edge weights as given.

2. Algorithm choice — 5 marks

Kruskal's algorithm. Sort all edges by non-decreasing weight. Process them in that order, adding an edge to the growing forest only if its two endpoints are currently in different components (i.e. adding it would not create a cycle); skip it otherwise. A disjoint-set (union–find) structure tracks components in near-constant time per operation. The process stops once $|V|-1$ edges have been added, at which point the forest is a single spanning tree, and — by the cut property (the lightest edge crossing any cut belongs to some MST) — it is guaranteed minimum.

3. Applying Kruskal — 3 marks

Approach. Sort the 12 edges by weight, then scan them in order, unioning components and recording an edge whenever its endpoints are not already connected; stop at 7 edges ($|V|-1=8-1$).

Sort edges by weight. $(a,b,1),(f,h,1),(f,g,2),(g,h,2),(a,c,3),(b,c,3),(b,e,4),(d,f,4),(d,g,4),(c,e,5),(e,g,5),(c,d,6)$.

Scan and union.

Edge (weight)	Endpoints' components before	Action
(a,b,1)	{a} , {b}	add — connects a,b
(f,h,1)	{f} , {h}	add — connects f,h
(f,g,2)	{f,h} , {g}	add — connects f,g,h
(g,h,2)	both in {f,g,h}	skip — would close a cycle
(a,c,3)	{a,b} , {c}	add — connects a,b,c
(b,c,3)	both in {a,b,c}	skip — cycle
(b,e,4)	{a,b,c} , {e}	add — connects a,b,c,e
(d,f,4)	{d} , {f,g,h}	add — connects d,f,g,h
(d,g,4)	both in {d,f,g,h}	skip — cycle
(c,e,5)	both in {a,b,c,e}	skip — cycle
(e,g,5)	{a,b,c,e} , {d,f,g,h}	add — connects all 8 vertices, 7th edge, stop

Result. $$\text{MST} = \{(a,b,1),(f,h,1),(f,g,2),(a,c,3),(b,e,4),(d,f,4),(e,g,5)\}, \qquad \boxed{w(\text{MST}) = 1+1+2+3+4+4+5 = 20}.$$

Figure 3 — Selected MST edges in bold blue; rejected (cycle-forming) edges dashed grey. The remaining edge $(c,d,6)$ was never even reached before the tree completed.

Quantity	Result
MST edge set	ab, fh, fg, ac, be, df, eg
Number of MST edges	7 (= \|V\| − 1)
Total MST weight	20

Concept & Theory

Topic. Minimum spanning trees; Kruskal's greedy algorithm and the cut property.

Key relations. Cut property: for any cut of the graph, the minimum-weight edge crossing it is in some MST. Cycle property: the maximum-weight edge on any cycle is in no MST. Running time with a union–find (path compression + union by rank): $O(E\log E)$, dominated by the initial sort.

Why this works. Each time Kruskal accepts an edge it is, by construction, the lightest edge available that crosses the cut between "the two components it merges" and everything else — the cut property guarantees that edge belongs to some MST, so greedily accepting the cheapest safe edge at every step never rules out optimality.

Common pitfall. Forgetting to skip an edge whose endpoints are already connected (this silently creates a cycle, producing a graph with too many edges rather than a tree) — visible above at $(g,h,2)$, $(b,c,3)$, $(d,g,4)$ and $(c,e,5)$, all rejected for exactly this reason. Prim's algorithm (grow a single tree from one start vertex, always adding the cheapest edge leaving the tree) is an equally valid answer to part 2 and gives the same total weight of 20 on this graph.

Source. Cormen, Leiserson, Rivest & Stein, Introduction to Algorithms §23 (minimum spanning trees, Kruskal & Prim).

Question 4 of 8: Spanning Tree

Question 4: Spanning Tree (10 marks: 2, 5, 3)

1. The graph — 2 marks

2. Algorithm choice — 5 marks

3. Applying Kruskal — 3 marks