Minimum Spanning Trees (Kruskal's Algorithm) (DP IB Applications & Interpretation (AI)): Revision Note

Kruskal's algorithm

How can I use Kruskal’s Algorithm to find a minimum spanning tree?

  • STEP 1
    Sort the edges in terms of increasing weight

  • STEP 2
    Select the edge of least weight

    • If there is more than one edge of the same weight then either may be used

  • STEP 3
    Look at the edge with the next least weight

    • If it would form a cycle with your currently selected edges then reject it

    • Otherwise, select it

  • STEP 4
    Repeat step 3 until all the vertices in the graph are connected

    • Count the number of edges

    • If there are n vertices then you stop once you have n-1 edges

Examiner Tips and Tricks

When Kruskal's algorithm, make sure that you state the order in which you consider the edges to get full marks for working! Also, show the edges that you reject.

Worked Example

Consider the weighted graph G below.

3-10-3-ib-ai-hl-minimum-spanning-trees-we-1

a) Use Kruskal’s algorithm to find the minimum spanning tree. Show each step of the algorithm clearly.     

3-10-3-ib-ai-hl-minimum-spanning-trees-w1a-solution

b) State the total weight of the minimum spanning tree.

3-10-3-ib-ai-hl-minimum-spanning-trees-w1b-solution

Unlock more, it's free!

Join the 100,000+ Students that ❤️ Save My Exams

the (exam) results speak for themselves:

Naomi C

Author: Naomi C

Expertise: Maths Content Creator

Naomi graduated from Durham University in 2007 with a Masters degree in Civil Engineering. She has taught Mathematics in the UK, Malaysia and Switzerland covering GCSE, IGCSE, A-Level and IB. She particularly enjoys applying Mathematics to real life and endeavours to bring creativity to the content she creates.

Dan Finlay

Reviewer: Dan Finlay

Expertise: Maths Subject Lead

Dan graduated from the University of Oxford with a First class degree in mathematics. As well as teaching maths for over 8 years, Dan has marked a range of exams for Edexcel, tutored students and taught A Level Accounting. Dan has a keen interest in statistics and probability and their real-life applications.