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 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
Examiner Tip
- Draw out the edges included in the minimum spanning tree as you go along as it will make it easier to spot potential cycles
- When using any of the algorithms for finding the minimum spanning tree, make sure that you state the order in which the edges are selected to get full marks for working!
- In Kruskal's algorithm, the edges are sorted into increasing weight first
- there are algorithms for that too !
Worked example
Consider the network below.
a)
Use Kruskal’s algorithm to find the minimum spanning tree. Show each step of the algorithm clearly.
- STEP 1
List the edges in order of increasing weight
EH (1)
DH (2)
AB (4)
EF (5)
FG (5)
BC (6)
BF (7)
CD (8)
GH (8)
AD (9)
AE (11)
CG (15)
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
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
Note that the edges EF and FG are of equal weight so could be added in either order
b)
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
