3. Algorithm For Computing a Minimum Spanning Tree

This algorithm is extremely similar to our shortest path algorithm. In the shortest path algorithm, the key ideas was to pick from READY the node that was closest to the starting point: to do this we needed to store extra information on the READY list along with each node - in particular we need to store the length of the shortest known path to the node from the starting point (we also stored the path itself).

In Minimum spanning tree (MST), the key idea is very similar: pick from READY the node that is closest to the spanning tree we have built so far. To do this we need to store extra information on the READY list along with each node: the length of the shortest known path to the node from any node in the tree built so far. We note that the shortest path to the nearest node (N) will always be a single edge, so to store the `path' leading to N will always involve just one other node (one that already in the MST), so along with N we will just store this node and the weight of the edge connecting them.

Minimum Spanning Tree (MST) algorithm

1. Pick any node X as your starting point. Place <X,empty path,0> on READY.

2. pick the triple <N,P,L> on READY such that L is minimum.
   • Process it. (print ``N is connected to P in the MST'')

   • Remove it from READY, and mark it as `processed'.

   • Look up N's neighbours {N1, N2...Nk}. These are connected to N by edges that have weights W1,W2,...Wk. Ignore those that are `processed'.

     For each neighbour Ni that is `unprocessed':

     • create the triple <Ni,N,Wi>

     • add this triple to READY - if there is already a triple for Ni on READY, only add the new one (and delete the old one) if its path length (weight) is smaller.

3. repeat 2 until READY is empty.

Example (MST):

• Step 1: READY = [<A,A,0>]

• Step 2: Process A, mark it `processed'. READY = [<B,A,7>, <C,A,2>]

• Step 2: Process C, mark it `processed'. C's unprocessed neighbours are B and D. Make up a triple for each of them: <B,C,4> <D,C,5>. Add these to READY if the node name is not already there, or if it is there but the new triple has a smaller path length (weight).

  In this case, we add the new D triple because D is new, and the new B triple because it has a smaller weight than the one on READY.

  READY = [<B,C,4>, <D,C,5>]

• Step 2: Process B, mark it `processed'. B's sole unprocessed neighbour is D. Create the triple <D,B,3>. This is added to READY, and the D-triple on READY is deleted, because the new triple has a smaller path length than the existing one.

• Step 2: Process D, mark it `processed'. D has no unprocessed neighbours. READY = [] (i.e. empty).

• C is connected to A in the MST.
• B is connected to C in the MST.
• D is connected to B in the MST.