Minimum Spanning Tree, 4 ways

← Home · Minimum spanning tree, four ways

Minimum spanning tree

Same idea, four ways to study it. Tap a style and find the one that clicks for you. 📺 Prefer to watch? Videos are on the lesson page.

🌳 Connect every vertex for the least total weight, no loops. Kruskal's: sort edges → add if no cycle → stop at n − 1 edges.

What it is

A spanning tree connects every vertex of a network with no cycles. The minimum spanning tree is the one with the smallest total edge weight, the cheapest way to keep everything connected. For n vertices it always has n − 1 edges.

Kruskal's algorithm

sort edges → add if no cycle → stop at n − 1

List the edges smallest weight first.
Add the smallest edge that does not create a cycle.
If an edge would make a loop, skip it.
Stop once you have n − 1 edges, everything's connected.

Worked example

Five towns, cable costs: A–B 4, A–C 8, B–C 3, B–D 6, C–D 5, C–E 7, D–E 2. Find the MST.

Edge (sorted)	Weight	Add?
D–E	2	✓
B–C	3	✓
A–B	4	✓
C–D	5	✓ (4th → done)
B–D, C–E, A–C	6, 7, 8	cycle / not needed

MST total = 2 + 3 + 4 + 5 = 14. With 5 towns, 4 edges.

Watch out

• Skip any edge that closes a cycle, even if it's small.
• Stop at exactly n − 1 edges, don't keep going.
• MST connects all vertices, shortest path links just two, different question.
• The total is the sum of the chosen edge weights.

The chosen edges, in gold

Gold edges (A–B, B–C, C–D, D–E) reach every town with the least total, 14. The grey chords were skipped: each would close a loop.

Why no loops

Any loop has one edge you don't need, you could already reach those vertices the other way round. Drop it and you save weight while keeping everyone connected. That's why a minimum spanning tree never contains a cycle.

Warm up first

Don't read yet, just have a go in your head:

A network has 6 vertices. How many edges in its MST?

n − 1 = 6 − 1 = 5 edges.

The next smallest edge would close a loop. What do you do?

Skip it and move to the next smallest.

Is MST the same as shortest path?

No. MST connects all vertices; shortest path links two.

Faded example: Kruskal's on five towns

Rung 1 · watch one done fully

Sorted: D–E 2, B–C 3, A–B 4, C–D 5, … Add D–E, B–C, A–B, C–D = 4 edges. Total = 2+3+4+5 = 14.

Rung 2 · you fill the gaps

After D–E (2), B–C (3) and A–B (4), the running total is ?. Adding C–D (5) makes the final total ?

Check my gaps

9, then 14.

Rung 3 · all you

Four towns, edges P–Q 5, P–R 9, Q–R 4, Q–S 8, R–S 6. Find the MST and its total. Check below.

Check my answer

Sorted: Q–R 4, P–Q 5, R–S 6, … Add Q–R, P–Q, R–S = 3 edges (n − 1), all connected. Total = 4 + 5 + 6 = 15.

Say it back

In one sentence, out loud: when do you skip an edge in Kruskal's algorithm?

⚡ Minimum spanning tree, one look

Spanning treeconnects all vertices, no cycles

Minimumthe spanning tree with the least total weight

Edgesalways n − 1 for n vertices

Kruskal'ssort edges → add if no cycle → stop at n − 1

Skip an edgeif it would close a loop (cycle)

ExampleD–E 2, B–C 3, A–B 4, C–D 5 → total 14

TrapMST ≠ shortest path · stop at n − 1 edges