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 chosenAdd 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
Examiner Tip
- 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!
Worked example
Consider the network below.
a)
Use Kruskal’s algorithm to find a minimum spanning tree for the network. 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
- STEP 5
List the edges in the order they were added
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
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
