7. The shortest spanning subtree of a graph.

I have chosen the following example for a variety of reasons. Firstly, although the final program is rather short, the solution is far from trivial. Secondly, our true subject matter is ''structure'' rather than straightforward numerical material, and as a result, the decisions taken to represent the information (using numerical values) are more manifest. Finally it presents us with a type of strategic decisions which are typical.

Two points can be connected by one point-to-point connection; three points can be connected with each other by two point-to-point connections; in general N points can be fully interconnected by N–1 point-to-point connections. Such a set of interconnections is called a ''tree''; the point-to-point connections that constitute the tree are called ''its branches''. Cayley has been the first to prove that the number of possible trees between N points equals NN–2.

We now assume that for each possible branch the length has been given. Defining the length of a tree as the sum of the lengths of its branches, we can ask for the shortest tree between those N points. (For the time being we assume that the given lengths are such that the shortest tree is unique. From our analysis it will follow that no two branches of equal length is a sufficient condition for this assumption.)

Note. The points don't need to lie in a Euclidean plane, nor do the given distances need to satisfy the triangle inequality.

An apparently straightforward solution would generate all trees between the N points, compute their lengths and select the shortest one, but Cayley's theorem shows that this would become very expensive as N increases. The following theorem enables us to find the shortest tree with considerably less work. Given a subtree of the shortest tree, then the shortest branch that can be found between one of the points touched by this subtree and one of the points not touched by this subtree will be part of the shortest tree between all N points.

This theorem is easily proved. Colour the branches of the subtree and all points connected to it red; colour all the remaining points blue and colour all branches leading from a red point to a blue one violet. The theorem asserts the shortest violet branch is part of the shortest tree as well. Call this shortest violet branch V and assume that it is not part of the shortest tree T; we shall then construct a tree T' which is shorter than T, thus arriving at a contradiction. Add to the tree T the violet branch V; in the resulting graph the violet branch must be contained in a closed loop. As this violet branch connects a red point with a blue one, it is clear that, going around the loop, we must find at least one other violet branch in this loop. Call this V' and remove V'. The resulting graph has again N–1 branches; it connects all N points (we have removed a branch from a loop) and therefore it is a tree connecting all N points. Call it T'. From T' = T + V – V' follows: length(T') = length(T) + length(V) - length(V') As V was the shortest violet branch, we have length (V) < length (V'), so that length (T') < length (T) i.e. the tree T cannot have been the shortest one.

The above theorem tells us that a red subtree of the shortest tree T can be extended with a point and the branch leading to it: the shortest violet branch and the blue point it leads to can be coloured red. As a result, if we can find a red subtree to start with, we can let it grow by one branch at a time. But it is very easy to start with a red subtree, viz. the red subtree consisting of a single point (any point will do) and no branches. Starting from the subtree we can let it grow to the shortest tree in N–1 steps, each step adding a new red branch and a new red point to it. We can represent the framework of this algorithm as follows:

COLOUR ONE POINT RED AND THE REMAINING ONES BLUE;
while NUMBER OF RED POINTS < N do
begin
  SELECT SHORTEST VIOLET BRANCH;
  COLOUR IT AND ITS BLUE ENDPOINT RED
end.

As it stands, the main task will be ''SELECT SHORTEST VIOLET BRANCH'', because the number of violet branches may be quite large, viz. k * (N – k) where k = NUMBER OF RED POINTS. If ''SELECT SHORTEST VIOLET BRANCH'' were an isolated operation, there is not much that could be done about it; in the above program, however, the operation has to be performed N–1 times in succession and the successive sets of violet branches are strongly related: they are the branches between red and blue points and each time only one point changes its colour. We would like to exploit this with the aim of reducing the set of branches from which each time the shortest branch should be selected: we are looking for a useful subset of the violet branches. We still don't know if such a really useful subset exists, but let us assume for the moment that it can be found and let us call it ''ultraviolet''. If such a set exists (each time) it is only helpful provided that we have a cheap way of constructing this subset, and our only hope is to be found in the past history of the computation, for instance the set of ultraviolet branches used the previous time. This suggests a program of the following structure:

COLOUR ONE POINT RED AND THE REMAINING ONES BLUE;
CONSTRUCT THE SET OF ULTRAVIOLET BRANCHES;
while NUMBER OF RED POINTS < N do
begin
  SELECT SHORTEST ULTRAVIOLET BRANCH;
  COLOUR IT AND ITS BLUE ENDPOINT RED;
  ADJUST THE SET OF ULTRAVIOLET BRANCHES
end.

where the set of ultraviolet branches should be defined in such a way that

  1. it is guaranteed to contain the shortest violet branch
  2. the set of ultraviolet branches is in general much smaller than the set called simply violet
  3. the operation ''ADJUST THE SET OF ULTRAVIOLET BRANCHES'' is cheap, for otherwise the profit we are trying to gain is lost.

Can we find such a definition of the concept ''ultraviolet''? Well, for lack of further knowledge I can only suggest that we try.

Considering that the set of violet branches leading from the k red points to the N–k blue ones has K * (N – k) members and observing criterion 1, two obvious possible subsets present themselves immediately:

  1. Make for each red point the shortest violet branch ending in it ultraviolet. In this case the set of ultraviolet branches has k members.
  2. Make for each blue point the shortest violet branch ending in it ultraviolet. In this case the set of ultraviolet branches has N–k members.

Our aim is to keep the ultraviolet subset small, but we won't get a clue from their size: with the first choice the sizes will run from 1 through N–1, with the second choice it will be the other way round. So, if there is any chance of deciding we must find it in the price of the operator ''ADJUST THE SET OF ULTRAVIOLET BRANCHES''.

Without trying the various adjustments of the ultraviolet sets, there is one observation which suggests a preference for the second choice. In the first choice k ultraviolet branches may lead from the red tree to the same blue point; then we know a priori that at most one of them will be coloured red, while with the second choice each blue point is connected in one way only to the red tree (the sum of the number of red and ultraviolet branches is then constantly equal to N–1) and it is possible that all ultraviolet branches at a certain moment will be eventually coloured red —in which case the adjustment operator was empty but for the removal of the one made red. Therefore, let us try the second choice for the criterion ultraviolet. (Initially this set comprises the N–1 branches leading from the one red point to the remaining N–1 blue ones, so that presents no problem.)

Consider now that we have a red subtree R and that from the corresponding set of ultraviolet branches (according to the second choice —I shall no longer repeat that qualification) the shortest branch leading to the blue point P and the blue point P itself have been coloured red. The number of ultraviolet branches has been decreased by 1 as it should be. Are the remaining ones the good ones? For each blue point they represent the shortest connection to the red tree R, and they should represent the shortest possible connection to the new red tree R + P. But this is settled by means of a simple comparison for each blue point B: if the branch BP is shorter than the ultraviolet branch connecting B to R, the latter is to be replaced by the branch BP —its colour is washed away and BP is made ultraviolet instead—; otherwise it is maintained, as the growth of the red tree with the point P did not provide a shorter way of connecting B with the red tree. As a result the cost of the adjustment operator —which has to deal with N–k blue points— is a linear function of N and k (and not quadratic as k * (N – k)), and the introduction of this concept of ultraviolet is indeed accomplishing the savings we were hoping for.

Exercise. Convince yourself that the rejected alternative of the concept ''ultraviolet'' is not so helpful.

Let us try to represent our algorithm in its current stage of refinement:

COLOUR ONE POINT RED AND THE REMAINING ONES BLUE;
CONSTRUCT THE SET OF ULTRAVIOLET BRANCHES;
while NUMBER OF RED POINTS < N do
begin SELECT SHORTEST ULTRAVIOLET BRANCH AND CALL ITS BLUE ENDPOINT P;
          COLOUR IT AND POINT P RED;
          ADJUST FOR EACH BLUE POINT B BY COMPARING WITH THE BRANCH BP
end.

By now the time has come to consider the representation of the information involved. We assume the N points numbered from 1 to N, we assume the length of the branches given by a two-dimensional array

real array distance[1:N, 1:N] ,

such that for 1 ≤ i, j ≤ N

distance[i, j] = distance[j, i] =
        length of branch connecting the points i and j.

The answer required is for a tree of N–1 branches, each branch being identified by the numbers of its endpoints; the answer is an (unordered) set of (unordered) pairs of numbers. We can represent then by two arrays:

integer array from, to[1:N–1]

where for each h satisfying 1 ≤ h ≤ N–1 the pair ''from [h], to [h]'' gives (the numbers of) the endpoints of the h-th branch. In our final solution the branches will be numbered (by h); the only order that makes sense is the order in which they have been coloured red. The observation made earlier that the total number of branches to be manipulated (red and ultraviolet together) remains constant suggests that we store them in the same array:

if k = NUMBER OF RED POINTS
         from[h], to[h] will be red for 1 ≤ h < k
         from[h], to[h] will be ultraviolet for k ≤ h < N .

The ultraviolet branches will be represented leading from a red point to a blue one. The array ''length'' has been introduced in order to reduce the number of subscriptions to be carried out:

length[h] = distance [from[h], to[h]] will hold (and will be restored immediately when temporarily invalid).

Point N is chosen as the initial point to be coloured red. ''SELECT SHORTEST ULTRAVIOLET BRANCH'' is a straightforward search for a minimum value. ''COLOUR IT AND POINT P RED'' is done by an interchange on the three arrays (if necessary), followed by an increase of k. In ''ADJUST FOR EACH BLUE POINT B BY COMPARING WITH THE BRANCH BP'', h scans the violet branches, to[h] will scan the blue points and len is used to store the length of branch BP. The final program is given on the next page.

Exercise.

Let distance [i,j] be the distance from point i to point j in that direction. As we may have one-way traffic, the relation distance[i,j] ≠ distance[j,i] is then permissable. Make a program finding in the graph the shortest path leading from point I to point J. This is a difficult exercise, therefore it is worth trying!

begin
  integer array from, to [1:N–1];
  real array length [1:N–1];
  real len, minlen;
  integer k, h, minh, p;

  COLOUR ONE POINT RED AND THE REMAINING ONES BLUE:
    k := 1;   CONSTRUCT THE SET OF ULTRAVIOLET BRANCHES:
    h := 1;
    while h < N do
    begin
      from[h] := N; to [h] := h; length[h] := distance[N,h]; h := h+1;
    end;
    while k < N do
    begin      SELECT SELECT SHORTEST ULTRAVIOLET BRANCH
      AND CALL ITS BLUE ENDPOINT P:
        minh := k; minlen := length[k]; h := k+1;
        while h < N do
        begin
          len := length[h];
          if len < minlen do
          begin
            minlen := len;
            minh := h;
          end
          h := h + 1;
        end;
        p := to[minh];       COLOR IT AND POINT P RED:
        if k ≠ minh do
        begin
          h := from[k];
          from[k] := from[minh];
          from[minh] := h;
          h := to[k];
          to[k] := to[minh];
          to[minh] := h;
          len := length[k];
          length[k] := length[minh];
          length[minh] := len;
        end;
        k := k + 1;       ADJUST FOR EACH BLUE POINT BY COMPARING WITH THE BRANCH BP:
        h := k;
        while h < N do
        begin
          len := distance[p, to[h]];
          if len < length[h] do
          begin
            length[h] := len;
            from[h] := p;
          end;
          h := h + 1;
        end;
    end;
  h := 1;
  while h < N do
  begin
    print(from[h]);
    print(to[h]);
    newline;
    h := h + 1;
  end;
end;

Back to top

Next chapter: 8. The towers of Hanoi