Kruskal's Algorithm (Edexcel International AS Maths): Revision Note

Kruskal's Algorithm

What is Kruskal's algorithm?

• Kruskal's algorithm is a mathematical tool that can be used to connect all of the vertices in a network in a way that reduces costs, materials or time

  • It achieves this by finding a minimum spanning tree (MST).

Why do we use Kruskal’s Algorithm?

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

• Finding a minimum spanning tree is useful in a lot of practical applications

  • 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