Building a Minimal Spanning Tree
|Figure 2. Spanning Skills: The red links show a spanning tree rooted at node A.|
A spanning tree
is a subset of links in a network that connect every node to an initial root node
. For example, Figure 2
shows a spanning tree rooted at node A
. By starting at node A
and following the red links, you can reach every node in the main body of the network. As you can see, there are no red links leading to nodes H
, and J
so you can't reach them from node A
The tree shown in Figure 2
is actually a shortest path tree rooted at node A
. See the previous article
about shortest paths for extra details, but for now just note that a shortest path tree is also a spanning tree.
If you add up the costs of the red links in Figure 2, you'll see that this spanning tree has a total cost of 57. A minimal spanning tree is a spanning tree that has the least possible total cost.
For example, in Figure 2 if you were to remove the B-D link from the tree and add the E-D link, you still have a spanning tree (there's still a path to node D). However, that tree's total cost is now only 55 because you removed a link with cost 7 and added one with cost only 5.
Figure 3 shows a minimal spanning tree for this network. Depending on a network's shape and costs, it may have more than one minimal spanning tree. This network has only one—the tree shown in Figure 3.
|Figure 3. Superior Spanning: The red links show a minimal spanning tree rooted at node A.|
Spanning trees are useful for finding the least expensive way to connect the nodes in a network. For example, suppose you want to build a network connecting a group of buildings or company sites. You could make a network that includes every possible link between sites. The network would not include impossible links such as those that cross rivers, government land that you don't have permission to cross, and so forth. Calculating the minimal spanning tree will show the cheapest way to build a network connecting your sites.
As another example, suppose you're designing an electrical circuit and you need to route power to specific spots (outlets in a house, locations on a chip, appliances on a boat, and so forth). The minimal spanning tree for that network shows the best way to run the power lines.
You can find a minimal spanning tree for a network by using a simple greedy algorithm. In each step of a greedy algorithm, the program makes a decision that works as much as possible towards a good solution. In the minimal spanning tree algorithm, that means adding the least expensive link to the tree that connects a new node to the tree.
Here's how the algorithm works:
- Add the root node to the spanning tree.
- While a node exists that's not connected to the spanning tree:
- Consider the links connecting nodes in the tree to nodes not in the tree. Add the least costly of those links to the tree.
shows the steps the spanning tree algorithm follows for this network. It starts by adding the root node A
to the tree.
|Figure 4. Spanning Step-by-Step: At each step, the program adds the least costly link that connects a new node to the tree.|
In the first step, the program considers the links leaving node A
that connect to nodes that are not in the tree. (Initially A
is the only node in the tree.) Those are the A
links with costs 10
. The A
link has a smaller cost so the program adds that one to the tree.
In step 2, the program considers the links leaving nodes in the tree leading to nodes not in the tree. That includes links A
. The C
link has the smaller cost of 4
so the algorithm adds that link to the tree.
In step 3, the links connecting new nodes to the tree are A-B, E-D, and E-F. The E-D link has the smallest cost of 5 so the program adds that link to the tree.
In step 4, the links connecting new nodes to the tree are A-B and E-F. The A-B link has the smaller cost of 10 so the program adds that link to the tree.
In step 5, the links B-D and B-E are now considered but they connect to nodes that are already in the tree so the algorithm ignores them. The only link connecting a node in the tree to a node that is not is the E-F link so the program adds it to the tree.
In step 6, the only link connecting a node in the tree to a node that is not is the F-G link so the program adds it to the tree.
The algorithm makes one more loop to consider the G-D link, discovers that the link connects to a node already in the tree, and stops.
The code in Listing 1 shows how NetAlgs finds minimal spanning trees.
In Listing 1, the call to ResetAlgorithms resets node and link properties, such as those that indicate whether a node is in the spanning tree. After resetting the algorithm properties, the program makes an empty list named cl to hold candidate links that might be good to add to the spanning tree. Initially the list is empty.
The program then enters a loop that runs until the tree is complete. Inside the loop, the program examines the links emanating from the most recently added node, and adds them to the candidate list. Initially that node is the tree's root node. (In Figure 4, the root node is A, and its links are A-B and A-C.)
Next the program loops through the candidate list removing any links that lead to nodes that are already in the spanning tree. Then it loops through the candidate list again, to find the remaining link with the smallest cost. If one exists, it adds that link and its destination node to the spanning tree. The program repeats this process until the candidate list is empty. At that point, every node reachable from the root node and the shortest link to that node is in the spanning tree.