Comparing MST Algorithms (Edexcel International A Level 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 both will 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 edges is available) 

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

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

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

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

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

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

  • it does not require checking for cycles at each step

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