Here’s a network with two minimal spanning trees:
Can you find both of them? It can be quite hard and take a long time.
Sometimes it is going to be very impractical to find a minimal spanning tree by eye. The following network represents a mycorrhizal nutrient transfer system:
A severe drought is affecting the area, so only the most essential connections can be sustained by the fungus. What is the shortest total distance that the mycorrhizal network needs to spread itself across, while still making sure that every plant is connected to every other one?
We need to find the minimal spanning tree. This particular network has 416 spanning trees, which one is minimal? To add up all their weights is 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. The algorithm was first created by Vojtech Jarník, a Czech mathematician, in 1930. Both Robert Prim (in 1957) and Edsger Dijkstra (in 1959) independently rediscovered it, though Prim’s work popularised its use.
Our fungus spanning tree has grown from the vertex F to cover every plant in the area, and it covers 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.
Prim’s algorithm (from a network):
Pick any vertex to start the spanning tree.
Locate the lowest weight edge connected to the spanning tree.
If this edge would create a cycle, reject it.
If there is more than one edge with the lowest weight, pick any of them.
Add this edge and the vertex at the other end to the spanning tree. If all vertices are part of the spanning tree, stop. Otherwise, repeat from step 2.
Which two of the following are possible minimal spanning trees?
What is the minimum time taken to build a network of tracks that connect each landmark?
Prim’s algorithm (from a network):
Pick any vertex to start the spanning tree.
Locate the lowest weight edge connected to the spanning tree.
If this edge would create a cycle, reject it.
If there is more than one edge with the lowest weight, pick any of them.
Add this edge and the vertex at the other end to the spanning tree. If all vertices are part of the spanning tree, stop. Otherwise, repeat from step 2.