Kruskal's Algorithm (Edexcel A Level Further Maths): Revision Note

Kruskal's algorithm

What is Kruskal's algorithm?

• In a situation that can be modelled by a network, Kruskal’s algorithm is a mathematical tool that can be used to connect all of the vertices in a way that reduces costs, materials or time by finding the minimum spanning tree (MST).

Why do we use Kruskal’s algorithm?

• Kruskal’s algorithm is a series of steps that when followed will produce the minimum spanning tree for a network

• Finding the minimum spanning tree is useful in a lot of practical applications as it connects all of the vertices in the most efficient way possible

• The number of edges in a minimum spanning tree will always be one less than the number of vertices in the graph

• A minimum spanning tree cannot contain any cycles.

What are the steps of Kruskal’s algorithm?

• STEP 1
  Sort the edges in terms of increasing weight

• STEP 2
  Select the edge of least weight

  • If there is more than one edge of the same weight, either may be used

• STEP 3
  Select the next edge of least weight that has not already been chosen

  • Reject it if it forms a cycle with the other selected edges

  • Otherwise, add it to your tree

• STEP 4

  Repeat STEP 3 until all of the vertices in the graph are connected

  • If there are n nodes then there will be n - 1 edges in the minimum spanning tree

• STEP 5
  List the edges in the minimum spanning tree in the order they were added