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

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