Kruskal’s algorithm: Yorkshire

Now that GigaFibre has connected the major cities in the UK together, they have turned their attention to connecting the regional cities together. First on the list of regions to plan is the Yorkshire region, home to the University of Leeds.

Your tasks

1. Using the distances supplied in the table below, can you identify where each of the towns are located in the diagram at the end of the page?
2. Using Kruskal’s algorithm, formulate a plan for connecting Doncaster, Harrogate, Huddersfield, Hull, Leeds, Scarborough, Wakefield and Whitby together in the most economical way.

The distances between each of the cities are in the table Distance between the regional cities – accessible version (PDF)

The geographical locations of each of the cities are identified as vertices in the figure below. An edge exists between the two cities if it is possible to build a fibre connection between them.

A full text description of the image is available below:

Connecting Yorkshire – image full text description (PDF)

Recap of Kruskal’s algorithm

Here is a recap of Kruskal’s algorithm, which can be used to produce a minimum spanning tree:

Kruskal’s algorithm

1. Take the edges of the graph and write them in a list ordering them by the number associated with each edge from lowest number to highest number. The lowest number should be at the top of the list an the highest number at the bottom of the list.
2. Starting from the top of the list, add the edge with the lowest number if by adding the edge it does not introduce a cycle into the graph. Cross the edge out if you have considered it.
3. Repeat step 2 until you have crossed all of the edges off of your list.

Solution

Click to the next step for the solution.