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