Minimum Spanning Trees (Kruskal's Algorithm) (DP IB Applications & Interpretation (AI)): Revision Note

Kruskal's Algorithm

In a situation that can be modelled by a graph, Kruskal’s algorithm is a mathematical tool that can be used to reduce costs, materials or time.

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 connected graph

• Finding the minimum spanning tree is useful in a lot of practical applications to connect 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 cycle is a walk that starts at a given vertex and ends at the same vertex.

  • A minimum spanning tree cannot contain any cycles.

What is 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 and add it to your tree provided that it does not make a cycle with any of the previously selected edges

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