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).

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.

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
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
STEP 5
List the edges in the minimum spanning tree in the order they were added

Draw the edges included in the minimum spanning tree as you go along
- This will make it easier to spot potential cycles
Remember to state the order in which the edges are selected to get full marks for working!

Consider the network below.

3-10-3-ib-ai-hl-minimum-spanning-trees-we-1

Use Kruskal’s algorithm to find a minimum spanning tree for the network. Show each step of the algorithm clearly.

EH (1)
DH (2)
AB (4)
EF (5)
FG (5)
BC (6)
BF (7)
CD (8)
GH (8)
AD (9)
AE (11)
CG (15)

STEP 2
Add the edge of least weight (EH)
STEP 3
Add the next edge of least weight (DH)
STEP 4
Repeat Step 3
Repeat adding the next edge of least weight each time (provided it does not create a cycle) until all vertices are connected
STEP 5
List the edges in the order they were added

_0QbiNdw_picture-1

Edges are added in the order: EH (1), DH (2), AB (4), EF (5), FG (5), BC (6), BF (7)

Note that the edges EF and FG are of equal weight so could be added in either order

State the total weight of the minimum spanning tree.

Add up the weights of the edges in the minimum spanning tree

1 + 2 + 4 + 5 + 5 + 6 + 7 = 30

Total weight = 30

Kruskal's Algorithm (Edexcel International A Level Maths: Decision 1)