Minimum spanning trees

Objective. Apply Prim and Kruskal algorithms.

1. Learn
2. Worked example
3. Practice
4. Feedback
5. Continue

Learn: the key idea

A minimum spanning tree is a subset of a graph's edges that connects all vertices with no cycles, using the smallest possible total edge weight. Algorithms such as Kruskal's (repeatedly adding the cheapest edge that doesn't form a cycle) or Prim's (growing a tree from a starting vertex by always adding the cheapest edge connecting to a new vertex) find this minimum efficiently. For example, applying Kruskal's algorithm to a network of towns and road costs finds the cheapest way to connect all towns without any redundant roads.

Worked example

A graph has edges AB=3, AC=5, BC=4, BD=6, CD=2. Use Kruskal's algorithm to find the total weight of the minimum spanning tree.

1 $Order edges by weight: CD=2, AB=3, BC=4, AC=5, BD=6$
2 $Add CD(2): connects C,D. Add AB(3): connects A,B. Both valid, no cycles yet$
3 $Add BC(4): connects the two components {A,B} and {C,D} into one, valid. All 4 vertices now connected with 3 edges$
4 $AC and BD would create cycles so are rejected; total weight = 2+3+4 = 9$

Answer: 9

Concept mastery

Based on your past attempts at this lesson — the question types to practise again come first.

Complete a practice set to see your concept breakdown here.

Practice

Practice happens on its own screen, one question at a time. Answers stay hidden until you submit yours, and you can stop and pick up at the same question later.

Start practising

Common mistake. Students using Kruskal's algorithm add an edge purely because it's the next cheapest, forgetting to check it doesn't create a cycle with edges already chosen. Always verify each new edge connects a previously unconnected vertex, or reject it as forming a cycle.

Your progress

Tick each step as you finish it. Your exact reading position is saved automatically, so Continue drops you back on the same line.

0 of 5 steps complete

Your place saves automatically as you read.

My dashboard