9.06 Minimal spanning tree algorithms

Sometimes the minimal spanning tree is not obvious and takes some time to find by eye. Where this is the case, we can use algorithms to find the minimal spanning tree more systematically.

 

Prim's algorithm

The following network represents a nutrient transfer system connecting fungus to the roots of plants:

A severe drought is affecting the area, so only the most essential connections can be sustained by the fungus.

Question: What is the shortest total distance that the network needs to spread itself across, while still making sure that every plant is connected to every other plant?

We need to find the minimal spanning tree. This particular network has $416$416 spanning trees. Which one has the minimum weight? We can try to find them all and add up all their weights, but it’s going to take a very long time.

Instead, we’re going to use a procedure called Prim’s algorithm to find the minimal spanning tree without having to find all the spanning trees.

We begin by picking any vertex. Let’s say we pick $F$F. We then highlight the lowest weight edge coming out of $F$F:

We then add this edge, and the vertex on the other side, to our spanning tree:

Then we do the same thing again! Highlight the edge of lowest weight coming out of our spanning tree:

We then add that edge, and its vertex, to the spanning tree:

Once again, we highlight the lowest weight edge coming out of the spanning tree:

This time, there are two candidates! Both $DC$DC and $DF$DF have weight $12$12. We can pick either one at this point:

The lowest weight edge coming out of the spanning tree is still the weight $12$12 edge $DF$DF:

We will reject edge $DF$DF, because it connects two vertices already in the tree. If this edge was added it would no longer be a tree.

We won’t ever consider the edge $DF$DF again. So we move on to highlighting the next lowest weight edge:

The edge $BF$BF doesn’t connect two vertices already in the tree, so we add it in to the growing spanning tree:

The next lowest weight edges are all weight $14$14 so we highlight them all:

Once again, we reject the edge $DB$DB since it connects vertices in the tree:

That leaves us with two choices:

We are free to pick either of these. We add in the edge $BA$BA and the vertex $A$A, growing the spanning tree by one vertex every step:

Now that we have included vertex $A$A, $EG$EG no longer has the lowest weight. The edge $AG$AG has weight $8$8.

When edge $AG$AG included, the next lowest weight edge connecting the spanning tree is $GH$GH of weight $7$7.

We add this edge and vertex in to the network, completing the procedure:

We can delete the unused edges to show the final minimal spanning tree.

Our fungus spanning tree has grown from the vertex $F$F to cover every plant in the area, and it covers $12+10+10+13+14+8+7=74$12+10+10+13+14+8+7=74 metres in total.

This procedure is guaranteed to find the minimal spanning tree every time. Much easier than finding all the spanning trees and adding up all their weights! Here’s a summary of the procedure.

 

Kruskal's algorithm

We are going to use a different procedure to find the minimal spanning tree, called Kruskal’s algorithm. It is quite similar to Prim’s algorithm in a lot of ways.

Consider the following network of towns in northern Victoria, with the weights representing the amount of cabling (in kilometres) 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.

Question: 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 choices of weight $26$26, so we highlighted them in blue.

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

Now the edge between Rainbow and Hopetoun connects two vertices that are already connected in a their own smaller tree, so we reject that edge. Add in the edge between Charlton and Boort as it is only adding a lone vertex.

We then highlight the next lowest weight edge, shown in green.

This edge adds a lone vertex again, so we add the edge in. We then highlight the next lowest weight edge:

This edge adds a lone vertex again, so we add in the edge. We then highlight the next lowest weight edges, which gives us three choices all of weight $38$38.

We add all three edges, one at a time, in any order we like, but making sure we still have a tree or multiple smaller trees. 

If we continue the algorithm, we add in the edge from Beulah to Birchip, and from Birchip to Dumosa.

 

Then the edge from Birchip to Donald is rejected, as this edge would make the network no longer a tree (there would be paths from towns back to themselves):

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 show the final minimal spanning tree.

To connect all the towns to the National Broadband Network with minimal cabling, 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: