Solution: Kruskal’s algorithm: Yorkshire

How did you do?

In the previous exercise, you were asked to a) work out where the towns were located on the map and b) apply Kruskal’s algorithm to find a solution to GigaFibre’s planning task to connect the cities in Yorkshire to their network.

Here’s the solution to b). First, we order the edges by their distance. The table below has the edges order in ascending order by their distance. Did you get this bit right?

You should next have worked your way down the list considering which edges to include in the design. If an edge introduces a cycle into the solution we remove it from the solution, ignore it, and then move on to the next edge.

The image below shows the edges used after applying Kruskal’s algorithm. So an optimum plan for GigaFibre’s network in the Yorkshire region includes connections between Huddersfield and Wakefield, Wakefield and Doncaster, Wakefield and Leeds, Leeds and Harrogate, Harrogate and Whitby, Whitby and Scarborough, and Scarborough and Hull. The sum of the connections included in the plan is 229 km.

Did you get it right?

A full text description of the image is available below:

Connecting Yorkshire solution – image full text description (PDF)