A top down unification of minimum cost spanning tree algorithms

The problem of the design of communications networks has spawned the development of many of the algorithms currently used to solve the minimum cost spanning tree problem. We show that three minimum cost spanning tree algorithms, those by Kruskal, Prim, and Esau and Williams, can be derived from a single problem specification using “specification and transformation by parts,” a methodology for deriving families of algorithms. This approach is an alternative to the Kershenbaum and Chou unification of spanning tree algorithms. Whereas the Kershenbaum & Chou approach might be called bottom up, this is a top down approach which shows the original unity of the algorithms which emerges from the statement of the problem and also the essential differences. Besides pedagogical and aesthetic value, we maintain that an understanding of the algorithms from this perspective may be helpful in network design and modification.