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 Tip
- 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!
