Kruskal’s Algorithms

---

Kruskal’s Algorithm
1.
To begin, select the edge of least weight.
2.
Find the next edge of least weight. If it would form a cycle with the edges already
selected, don’t choose it. If not then add it to the MST.
3.
If there is a choice of equal edges, it has no effect which you choose first.
4.
Repeat step 2 until all vertices are connected.
Note: Kruskal’s algorithm is a greedy algorithm which is where it builds up a solution piece
by piece, always choosing the next piece that offers the most obvious and immediate
benefit.
The purpose of Kruskal’s Algorithm is to find a subset of the edges that forms a tree and
includes every vertex where the total weight of all of the edges is a minimum.
Kruskal’s algorithm is most suitable for sparse graphs (low number of edges).
Additional Questions
Question 1
Seán’s local football team is in the county final and his housing estate wants
to show their support by lining the roads with bunting. They want each
house to have bunting but they want to use the least amount of it.
(a) The number on each edge below represents the distance, in metres,
between each house. If x = 4, How much bunting do they need?
(b) What could the variable, x, represent in a different scenario? What
might affect it?
Question 2
In New York, there is a park with famous statues that has many visitors each
day. Lighting is to be installed at 5 places in the park (as shown) with the
places being connected either directly or indirectly by cabling following the
given paths.
The values on each edge represent the distance (in m) between each light. 
(a) Calculate the shortest length of cabling required and show the
minimum spanning tree (MST).
(b) State two differences between Kruskal’s algorithm and Prim’s
algorithm for finding a minimum spanning tree.
Question 3
For the network below, a student has commenced
finding the minimum spanning tree (MST) using
Kruskal’s algorithm. The student’s work is highlighted in
red.
Is the student’s work correct so far? If not, please correct
it. Complete the MST to determine the weight of the tree.
www.pdst.ie/pp/sc/applied-maths
1

---

Question 4
(a) When would you choose to use Kruskal’s algorithm over Prim’s algorithm?
(b) Draw a network in which:
(i) The three shortest edges form part of the minimum spanning tree.
(ii) Not all of the three shortest edges form part of the minimum spanning tree.
Question 5
(a) What is meant by the term ‘greedy algorithm’?
(b) A new broadband company wishes to lay new fibre optic
cables in County Cork so that every house has access to
broadband. It costs €350 per km to lay the cable. Calculate
the total cost of the project. Each weight on the diagram
represents distance in km.
Question 6
Your local area is having a new broadband network installed. The initial phase is to first
connect the post office, a shop, a sports club, primary school and secondary school.
(a) Using Google Maps (or another mapping tool), create a network with the locations
identified by nodes and the roads and distances represented by edges and weights.
(b) Using Kruskal’s algorithm, identify the length of cabling required and show the
minimum spanning tree.
Question 7
(a) Does Kruskal’s algorithm begin by selecting an edge or node?
(b) The diagram below represents a network of paths in a park. The number on each
edge represents the length of the path in metres.
Using Kruskal’s algorithm, find a minimum spanning tree for the network in the
diagram and state its total length.
www.pdst.ie/pp/sc/applied-maths
2

---

Solutions:
Question 1
(a) Total length = 21 m
(b) In a different context the weight could
represent cost, time, etc. and could be affected by
economics, availability (cost) or traffic, skill level (time).
Question 2
(a) Weight = 21 m
(b) Prim’s starts with a node. Kruskal’s starts with an edge.
Prim can start with any vertex while Kruskal must start with the edge of least weight.
The tree grows in a connected fashion when using Prim while Kruskal’s can grow
separately.
Question 3
Weight = 37
Question 4
(a) Kruskal’s algorithm should be used for sparse graphs (low number of edges) and
Prim’s algorithm should be used for dense graphs (high number of edges).
(b)
www.pdst.ie/pp/sc/applied-maths
3

---

Question 5
(a) A greedy algorithm is an algorithm that builds up a solution
piece by piece, always choosing the next piece that offers the
most obvious and immediate benefit.
(b) Weight = 41 km, Cost = €14,350
Note: This is one of many valid solutions.
Question 7
(a) Kruskal’s algorithm begins by selecting the edge of least weight.
(b) Total length = 110 m
www.pdst.ie/pp/sc/applied-maths
4