Applying Kruskal’s algorithm to the GigaFibre scenario

Now you have looked at the algorithm, it’s time to apply it!

In this step you will apply Kruskal’s algorithm to the GigaFibre scenario, working through it step by step. We have set it out just like an algorithm, hence its repetitive nature.

Follow it through below and see if it gets you to the same answer as you did in a previous activity.

Applying Kruskal’s algorithm: step 1

In step 1 of Kruskal’s algorithm each of the edges are listed in the graph ordered by the number associated with each edge. The table below lists the edges in ascending order starting from the smallest number at the top:

Applying Kruskal’s algorithm: step 2

Moving on to Step 2 of Kruskal’s algorithm, add the first edge in the list. (As there are no edges at the moment the inclusion of the edge won’t create a cycle.) Consequently, the edge between Manchester and Leeds is added.

The figure below illustrates this. The thicker line indicates the inclusion of the edge into GigaFibre’s network.

Applying Kruskal’s algorithm: step 3

Step 3 of Kruskal’s algorithm repeats step 2 as there are still edges in the list which are not crossed off. In step 2 of Krukal’s algorithm the next edge in the list is added, from the top (so long as it doesn’t make a cycle). This next edge is Glasgow to Edinburgh. The inclusion of the edge does not create a cycle, so it is included in GigaFibre’s network.

The figure below illustrates which edges have now been included:

Next, we repeat step 2 as there are still edges in our list which are not crossed off. In step 2 of Kruskal’s algorithm we add the next edge in the list, from the top (so long as it doesn’t make a cycle). The next edge is Lancaster to Manchester. The inclusion of the edge does not create a cycle, so we include it in to GigaFibre’s network.

The figure below illustrates which edges have now been included:

Next, we go back again to step 2 of Kruskal’s algorithm, of course, because there are still edges in our list which are not crossed off. In step 2 of Kruskal’s algorithm we add the next edge in the list, from the top (so long as it doesn’t make a cycle). The next edge is Lancaster to Leeds. Now, the inclusion of the edge introduces a cycle between Leeds, Manchester and Lancaster. So we do not add this edge into GigaFibre’s network.

(Why would adding the edge to the network not make a minimum cost network? To connect 3 cities together we only need 2 edges, the third would just be a waste.)

Next, we repeat step 2 of Kruskal’s algorithm as there are still edges in our list which are not crossed off. In step 2 we add the next edge in the list, from the top, so long as it doesn’t make a cycle. The next edge is Grantham to Birmingham. The inclusion of the edge does not create a cycle, so we include it in to GigaFibre’s network. The figure below illustrates what edges have so far been included in this exercise:

Moving on again (do you notice the algorithm in these steps?)we go back to step 2 of Kruskal’s algorithm as there are still edges in our list which are not crossed off. In step 2 we add the next edge in the list, from the top (so long as it doesn’t make a cycle). The next edge is Newcastle to Leeds. The inclusion of the edge does not create a cycle, so we include it in to GigaFibre’s network.

The figure below illustrates what edges have now been included:

Moving on, we go back to step 2 of Kruskal’s algorithm as there are still edges in our list which are not crossed off. In step 2, we add the next edge in the list, from the top (so long as it doesn’t make a cycle). The next edge is Manchester to Birmingham. The inclusion of the edge does not create a cycle, so we include it in to GigaFibre’s network.

The figure below illustrates what edges have been included so far in this exercise:

Once again, we go back to step 2 as there are still edges in our list which are not crossed off. In step 2 of Kruskal’s algorithm we add the next edge in the list, from the top (so long as it doesn’t make a cycle). The next edge is Grantham to Leeds. The inclusion of the edge introduces a cycle between Leeds, Manchester, Birmingham and Grantham, so we do not add this edge into GigaFibre’s network.

And here we are again, moving on an repeating step 2 as there are still edges in our list which are not crossed off. In step 2 of Kruskal’s algorithm we add the next edge in the list, from the top (so long as it doesn’t make a cycle). The next edge is Birmingham to Bristol. The inclusion of the edge does not create a cycle, so we include it in to GigaFibre’s network.

The figure below illustrates what edges have been included so far:

Once again, we repeat step 2 as there are still edges in our list which are not crossed off. In step 2 of Kruskal’s algorithm we add the next edge in the list, from the top (so long as it doesn’t make a cycle). The next edge is Newcastle to Lancaster. The inclusion of the edge introduces a cycle between Leeds, Manchester, Lancaster and Newcastle, so we do not add this edge into GigaFibre’s network.

Moving onwards again, we repeat step 2 as there are still edges in our list which are not crossed off. In step 2 of Kruskal’s algorithm we add the next edge in the list, from the top (so long as it doesn’t make a cycle). The next edge is Cardiff to Birmingham. The inclusion of the edge does not create a cycle, so we include it in to GigaFibre’s network.

The figure below illustrates what edges have been included now:

And again, we repeat step 2 as there are still edges in our list which are not crossed off. In step 2 of Kruskal’s algorithm we add the next edge in the list, from the top (so long as it doesn’t make a cycle). The next edge is Newcastle to Edinburgh. The inclusion of the edge does not create a cycle, so we include it in to GigaFibre’s network.

The figure below illustrates what edges have been included so far in this exercise:

Moving on to step 3 of Kruskal’s algorithm, we go back to Step 2 as there are still edges in our list which are not crossed off. In step 2 of Kruskal’s algorithm we add the next edge in the list, from the top, so long as it doesn’t make a cycle. The next edge is Grantham to London. The inclusion of the edge does not create a cycle, so we include it in to GigaFibre’s network. The figure below illustrates what edges have been included.

Moving on again, we go back to step 2 as there are still edges in our list which are not crossed off. In step 2 of Kruskal’s algorithm we add the next edge in the list, from the top (so long as it doesn’t make a cycle). The next edge is Birmingham to London. The inclusion of the edge introduces a cycle between Birmingham, Grantham and London. We do not add this edge into GigaFibre’s network.

And we move on again, back to step 2 as there are still edges in our list which are not crossed off. In step 2 of Kruskal’s algorithm we add the next edge in the list, from the top (so long as it doesn’t make a cycle). Are you thinking lik an algorithm yet? The next edge is Bristol to London. The inclusion of the edge introduces a cycle between Birmingham, Grantham, London and Bristol, so we do not add this edge into GigaFibre’s network.

Continuing on, we repeat step 2 because there are still edges in our list which are not crossed off. In step 2 of Kruskal’s algorithm we add the next edge in the list, from the top (so long as it doesn’t make a cycle). The next edge is Newcaste to Glasgow. The inclusion of the edge introduces a cycle between Glasgow, Edinburgh and Newcastle. We do not add this edge into GigaFibre’s network.

Finally!

Finally, we observe that there are no more edges to consider so the algorithm terminates and we have completed the planning of GigaFibre’s network.

How did you find thinking like an algorithm?