Section 6-3-1

6.3.1 Solving the MST Problem

The solution of MST problems turns out to be very simple. Of the several efficient algorithms that have been proposed for it, some are more useful for manual computations and others more suitable for computer applications. All the algorithms derive their validity from the following property of minimum spanning trees.

Fundamental property of MST's. Suppose that a procedure for finding the MST of any graph G has been discovered and that in the course of the construction of the MST, by using this procedure, the set N of nodes of G has been partitioned into k distinct trees T₁(N₁, A₁), T₂(N₂ A₂), ..., T_k(N_k, A_k) with N₁ N₂ ... N_k = N and N_i N_j = for i, j = 1, 2, ..., k (i j). By the construction assumption T₁, T₂, ... , T_k will eventually become constituent parts of the MST. Note that a "tree" may also consist of a single node of G. Now let T_s be one of these trees and let (i^*, j^*) be the shortest link with the property that one of its roots, node i^*, is in the tree T. and the other root, node j^*, is not in the tree T_s. Let T_t be the tree to which j^* belongs. It is then true that the link (i^*, j^*) must be a link in the final MST and that, therefore, trees T_s and T_t can be connected next through link (i^*, j^*)

Proof: (By contradiction) Assume that (i^*, j^*) is not part of the final MST, which, however, must, by assumption, contain both the tree T_s and the tree T_t. By definition of the MST, there is exactly one path leading from T_s to T_t. Let then (i, j) be that link on the MST which has one of its roots, i, in T_s and the other, j, not in T_s and which is the first link on the path from T_s to T_t (It is possible that i = i^* or that j = j^*.) By definition of (i^*, j^*), l(i, j) > l(i^*, j^*). If we then replace (i, j) by (i^*, j^*), a new spanning tree will result which will have less total length than the MST--a contradiction.

Note that in stating the property above we did not make any specific assumptions about the procedure for constructing the MST. We can then begin the procedure with n trees (where n is the number of nodes in the set N), with each tree consisting of a single isolated node and no links. We can then, according to the property that we proved, connect any arbitrarily chosen tree (node) to its nearest tree (node) and continue this procedure until all nodes are finally connected. Before proceeding to describe the details of this algorithm, we state the following corollary to the fundamental property of the MST's that we have proven:

Corollary: In an undirected network, G. the link of shortest length out of any node is part of the MST.

Proof: Follows directly from the fundamental property of MST's.

This corollary can be used to speed up the algorithmic procedure outlined below. However, it will not be explicitly included here.

MST Algorithm (Algorithm 6.3)

STEP 1	Begin the construction of the minimum spanning tree at some arbitrary node, say node i. Find the node closest to i, say j,⁹ and connect it to i (i.e., find the shortest link out of i and include it in the tree together with the node at its other end). Break ties, if any, arbitrarily.
STEP 2	If all nodes have been connected, stop, the minimum spanning tree has been obtained. If there are still isolated nodes, go to Step 3.
STEP 3	Find the one among the still isolated nodes which is closest to the already connected nodes and connect it with the already connected nodes (i.e., find the shortest link from the connected nodes to isolated nodes and include it in the tree together with the node at its other end). Break ties, if any, arbitrarily. Return to Step 2.

Example 5: MST

For the graph shown in Figure 6.11a, the algorithm above works as follows. Suppose that we choose arbitrarily to begin construction of the MST at node A. Since node G is closest to A, G and the link (A, G) first become part of the MST. There is next a tie between C and F as the next node to be connected to the MST (C is 6 units away from A and F 6 units away from G). We break the tie arbitrarily in favor of F. and link (G. F) and the node F are thus included in the MST. Proceeding in this way, nodes E, D, C, and B ire this order, are subsequently included in the MST, resulting in the MST shown in Figure 6.11b with a total length of 32 units.

Obviously, the most time-consuming of our MST algorithm's steps is the one that involves finding the next node to be included in the MST. This, in effect, means comparing the lengths of all links leading from nodes already included in the MST to nodes not included in the MST to find the shortest one. Repeated application of this step is computationally expensive. To overcome this problem, an alternative algorithm calls for the ranking of all links in G according to length and then the addition to the MST at each stage of the shortest link such that no cycle is formed with previously chosen links. Unfortunately, this approach also suffers from a computational disadvantage: checking for cycles--a trivial task in the case of manual solutions--is nontrivial in the case of computer applications and becomes "expensive', for large problems.

Finally, we note that whenever, in the course of applying Algorithm 6.3, a tie arises (and is broken arbitrarily), this raises the possibility that two or more minimum spanning trees of the graph G exist. Although the total length of all of these tied MST,s will be the same, they may differ markedly from each other in terms of which links each of them includes.

Exercise 6.2 Show that Algorithm 6.3 can be executed in O(n²) time.

⁹ The algorithm assumes n 2, the case n = 1 is trivial.