Comparing MST Algorithms (Edexcel A Level Further Maths): Revision Note

Naomi C

Author

Naomi C

Last updated

Comparing MST Algorithms

Which should I use - Prim’s or Kruskal’s algorithm?

  • Both algorithms find a minimum spanning tree

    • they may give different answers but will both produce a minimal solution

  • Prim’s algorithm can be used in either graph or matrix form

    • If an MST is asked for and the information is given in table/matrix form, use Prim’s algorithm

  • Kruskal’s algorithm can be used when the information is in graph form (or if a list of arcs is available) 

    • If trying to use Kruskal's algorithm from a table/matrix, it would be best to draw a graph first

  • Kruskal's algorithm allows arcs to be added in any order

    • i.e.  the tree can be 'split' (unconnected) at stages of the algorithm

    • Prim's algorithm 'builds' as arcs are added such that they will connect to arcs already in the tree

  • Prim’s algorithm is sometimes considered to be more efficient that Kruskal’s algorithm as

    • the edges do not need to be ordered at the start and

    • it does not rely on checking for cycles at each step

  • An exam question will usually specify which method should be used, otherwise either is fine

Examiner Tips and Tricks

  • A common exam question is to state that certain edges need to be included in a spanning tree

    • you are then asked to describe which algorithm you should use and how it should be adapted

    • you should start off by drawing in the edges given, and then complete the tree using Kruskal's algorithm!

👀 You've read 1 of your 5 free revision notes this week
An illustration of students holding their exam resultsUnlock more revision notes. It's free!

By signing up you agree to our Terms and Privacy Policy.

Already have an account? Log in

Did this page help you?

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.

Download notes on Comparing MST Algorithms