11.26 Practice Exercises

Minimum spanning tree algorithms become useful only after you can recognize the pattern in unfamiliar problems.

algorithmsgraphsspanning-trees

11.26 Practice Exercises

Problem

Minimum spanning tree algorithms become useful only after you can recognize the pattern in unfamiliar problems.

The core ideas are simple:

connect all vertices
minimize edge cost
avoid cycles
merge components

But problem statements rarely say “use Kruskal” or “use Prim.” They describe networks, roads, cables, clusters, islands, sensors, or regions. Your task is to translate the story into a graph and then choose the right MST tool.

This section provides practice exercises that reinforce the main techniques from the chapter.

Exercise 1: Basic MST

You are given this undirected weighted graph:

Edge Weight
A-B 4
A-C 2
B-C 1
B-D 5
C-D 8
C-E 10
D-E 2

Find the MST cost and selected edges.

Expected Approach

Use Kruskal.

Sort edges:

B-C = 1
A-C = 2
D-E = 2
A-B = 4
B-D = 5
C-D = 8
C-E = 10

Accept:

B-C
A-C
D-E
B-D

MST cost:

1 + 2 + 2 + 5 = 10

Exercise 2: Detect a Disconnected Graph

Input:

V = {A, B, C, D, E}

Edges:
A-B = 3
B-C = 4
D-E = 2

Does an MST exist?

Expected Answer

No.

The graph has two components:

{A,B,C}
{D,E}

A spanning tree must connect every vertex.

The correct output is either:

no spanning tree

or a minimum spanning forest:

A-B
B-C
D-E

depending on the API contract.

Exercise 3: Equal Weights

Graph:

A-B = 1
B-C = 1
C-D = 1
D-A = 1
A-C = 1

How many edges should an MST contain, and what is its cost?

Expected Answer

There are four vertices, so an MST contains:

3

edges.

Each selected edge has weight:

1

MST cost:

3

Many different MSTs exist. Do not require one exact edge set.

Exercise 4: Parallel Edges

Graph:

A-B = 10
A-B = 2
B-C = 3
A-C = 100

Find the MST.

Expected Answer

Use the cheaper parallel edge:

A-B = 2

Then select:

B-C = 3

MST cost:

5

The edge:

A-B = 10

is ignored.

Exercise 5: Negative Weights

Graph:

A-B = -4
B-C = 2
A-C = 5

Find the MST cost.

Expected Answer

MST algorithms allow negative weights.

Select:

A-B = -4
B-C = 2

Cost:

-2

Exercise 6: Cut Property

Graph:

A-B = 7
A-C = 2
B-D = 3
C-D = 5

Consider the cut:

S = {A}
V - S = {B,C,D}

Which edge is safe by the cut property?

Expected Answer

Crossing edges:

A-B = 7
A-C = 2

The lightest crossing edge is:

A-C = 2

So A-C is safe.

Exercise 7: Cycle Property

Cycle:

A-B = 2
B-C = 3
C-D = 4
D-A = 10

Which edge can never appear in any MST?

Expected Answer

The unique heaviest edge is:

D-A = 10

By the cycle property, it cannot appear in any MST.

Exercise 8: Kruskal Trace

Edges:

0-1 = 1
1-2 = 2
0-2 = 3
2-3 = 4
1-3 = 5

Trace Kruskal's algorithm.

Expected Trace

Sorted order is already shown.

Process:

0-1: accept
1-2: accept
0-2: reject, cycle
2-3: accept
1-3: reject, cycle

MST edges:

0-1
1-2
2-3

Cost:

7

Exercise 9: Prim Trace

Graph:

A-B = 4
A-C = 2
B-C = 1
B-D = 5
C-D = 8
C-E = 10
D-E = 2

Run Prim starting from A.

Expected Trace

Start at A.

Choose:

A-C = 2
C-B = 1
B-D = 5
D-E = 2

MST cost:

10

The order may vary with tie-breaking in other graphs, but the final cost must match Kruskal.

Exercise 10: Bottleneck Value

MST selected edge weights:

1, 2, 4, 7

What is the bottleneck value?

Expected Answer

The bottleneck value is the largest selected edge:

7

Every MST is also a minimum bottleneck spanning tree.

Exercise 11: Clustering

MST edges:

A-B = 1
B-C = 2
C-D = 10
D-E = 2
E-F = 1

Create two clusters.

Expected Answer

Remove the largest MST edge:

C-D = 10

Clusters:

{A,B,C}
{D,E,F}

Exercise 12: Maximum Spacing k-Clustering

Sorted edges:

A-B = 1
B-C = 2
D-E = 2
C-D = 9
E-F = 10

Using Kruskal, stop when k = 2 components remain. What is the spacing?

Expected Answer

Merge:

A-B
B-C
D-E

Now components include:

{A,B,C}
{D,E}
{F}

That is three components, so continue if all six vertices are included.

Next edge:

C-D = 9

would merge {A,B,C} and {D,E}, leaving:

{A,B,C,D,E}
{F}

Now k = 2.

The spacing is the next edge connecting different components:

E-F = 10

Exercise 13: Dense Graph Choice

You receive a complete cost matrix for 5,000 vertices.

Which MST algorithm should you consider first?

Expected Answer

Use matrix-based Prim.

The graph is dense and already represented as a matrix.

Avoid building and sorting all O(V²) edge objects unless there is a strong reason.

Exercise 14: Sparse Edge List Choice

You receive a file with one edge per line:

u v weight

The graph has:

V = 1,000,000
E = 3,000,000

Which MST algorithm is the natural first choice?

Expected Answer

Kruskal is a natural first choice because the input is already an edge list and the graph is sparse.

Use optimized union-find and sort edges by weight.

Exercise 15: Prim Bug

A Prim implementation updates candidate cost like this:

newCost = best[u] + weight(u, v)

What is wrong?

Expected Answer

That is Dijkstra-style accumulated distance.

Prim should use only the edge weight:

newCost = weight(u, v)

Prim minimizes total tree cost by repeatedly choosing the cheapest connecting edge, not the shortest path from the start vertex.

Exercise 16: DSU Bug

A Kruskal implementation checks:

if u != v:
    accept edge

What is wrong?

Expected Answer

It compares vertex IDs, not components.

The correct check is:

if find(u) != find(v):
    accept edge

Otherwise the algorithm may accept cycle-forming edges.

Exercise 17: Output Validation

An MST function returns five edges for a graph with five vertices.

Is the output valid?

Expected Answer

No, not for a connected spanning tree.

A tree with five vertices must contain:

V - 1 = 4

edges.

Five edges imply a cycle.

Exercise 18: Second-Best MST

MST cost:

20

A non-tree edge has weight:

7

The maximum edge on the MST path between its endpoints has weight:

5

What is the candidate tree cost?

Expected Answer

Use:

mstCost + w - pathMax

So:

20 + 7 - 5 = 22

Candidate cost:

22

Exercise 19: Missing Matrix Edge

An adjacency matrix uses:

-1

for missing edges.

Why is it wrong to treat -1 as a real edge weight?

Expected Answer

A missing edge is not a negative-cost edge.

Treating -1 as a real edge can cause the MST algorithm to select connections that do not exist.

The implementation must explicitly skip sentinel values.

Exercise 20: Overflow

An MST contains four selected edges:

1,500,000,000
1,500,000,000
1,500,000,000
1,500,000,000

What type should store the total cost?

Expected Answer

The total is:

6,000,000,000

This exceeds signed 32-bit range.

Use a 64-bit integer or another sufficiently wide numeric type.

Exercise 21: Borůvka Phase

Why should a Borůvka implementation first record every component's cheapest outgoing edge and only then perform unions?

Expected Answer

All choices in a phase should be based on the same component partition.

If components are merged while cheapest edges are still being computed, later decisions may use a different partition and produce incorrect or hard-to-debug behavior.

Exercise 22: Forest Size

A graph has:

V = 10
C = 3 connected components

How many edges should its minimum spanning forest contain?

Expected Answer

A forest over C components contains:

V - C

edges.

So:

10 - 3 = 7

Exercise 23: Algorithm Selection

You need an MST for a graph partitioned across many machines.

Which algorithmic family is most appropriate?

Expected Answer

Use a Borůvka-style or Borůvka-hybrid approach.

Borůvka exposes component-level parallelism and supports graph contraction, which are both useful in distributed systems.

Exercise 24: Self-Loop

Graph:

A-A = -100
A-B = 3
B-C = 4

Should the self-loop be selected?

Expected Answer

No.

A self-loop connects a vertex to itself and does not help connect components.

The MST uses:

A-B
B-C

Cost:

7

Exercise 25: Build a Test Plan

List five edge cases every MST implementation should test.

Expected Answer

A strong answer includes at least five of:

single vertex
disconnected graph
equal weights
parallel edges
negative weights
self-loops
large weights causing overflow
dense matrix input
sparse edge-list input
multiple valid MSTs

Recipe

To practice MST algorithms effectively:

  1. Trace Kruskal by hand.
  2. Trace Prim by hand.
  3. Use the cut property to justify selected edges.
  4. Use the cycle property to reject edges.
  5. Test equal weights and disconnected graphs.
  6. Compare algorithm choices for sparse and dense inputs.
  7. Validate both tree structure and cost.
  8. Revisit second-best MST and clustering as exchange-based extensions.

These exercises consolidate the chapter’s main patterns. If you can solve them without guessing, you have the working toolkit needed for MST problems in interviews, programming contests, graph libraries, and infrastructure design systems.