Networks

Lesson

We are going to use a different procedure to find the minimal spanning tree, called **Kruskal’s algorithm**, though it is quite similar to Prim’s algorithm in a lot of ways. It was first published in 1956 by mathematician and computer scientist **Joseph Kruskal**.

Consider the following network of towns in northern Victoria, with the weights representing the amount of cabling (in kilometers) required to connect two towns to the National Broadband Network:

In order to give each town access to the network, we only need to select edges for cabling that form a spanning tree. What is the minimum length of cabling required?

First, we **find the lowest weight edge** in the network. It becomes the start of our spanning tree.

Then we **find the next lowest** weight of all the remaining edges. This time there are two, and we highlight them:

We add these edges in and highlight the edges of the next lowest weight:

Now the edge between Rainbow and Hopetoun forms a cycle, so we **reject** that edge. The edge between Charlton and Boort is fine, though:

We then move up to the next lowest weight edge:

That one doesn’t form a cycle, so we add it in, and move up to the next lowest weight edge:

And again, as before:

Now there are three edges to consider. We add them in one at a time, in any order we like, but we still can’t make cycles. We add in the edge from Beulah to Birchip:

Then from Birchip to Dumosa:

Then the edge from Birchip to Donald is **rejected**, as it forms a cycle:

At this point we can see that only one vertex is left. All the edges connecting towns already in the spanning tree can be rejected straight away, and the lowest edge connecting Sea Lake to the network can be highlighted:

This is the last edge we need to complete the spanning tree. We add it in and delete the unused edges to see our result:

To connect all the towns to the National Broadband Network, we would need to lay:

$50+18+26+34+38+38+35+26+31=296$50+18+26+34+38+38+35+26+31=296 km of cabling.

Here’s a summary of the procedure:

Kruskal's Algorithm

- Locate the
**lowest weight edge**in the network. - If there is more than one,
**pick any one**. - If adding the edge to the spanning tree would create a cycle,
**reject it**. Otherwise, add it to the spanning tree. - If all vertices are part of the spanning tree,
**stop**. Otherwise,**repeat from step 1**.

Which algorithm do you prefer? Kruskal's, or Prim's?