Make your own free website on Tripod.com

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.

  3. repeat 2 until READY is empty.

Example (MST):

        
The output produced by this algorithm is: It should be clear that if you swapped the weights of the edges connecting D to B and C, then D would be connected to C in the minimum spanning tree.