#### Testing the MST

Proving your MST algorithm has two parts:- Proving that a spanning tree is produced
*and* - Proving that it's the
**minimum**spanning tree.

*etc*) on which the MST algorithm relies are performing correctly

you could do something like exhaustively generate*or***all**the possible trees and thus demonstrate that indeed the tree produced by your program was a MST.For maximum marks, you were expected to

*address*both parts of the problem in your report and do something about the first part.One of the post-conditions of your

`MST`method should have been:The tree produced is a spanning tree.

Adding an additional method`SpanningTree( Graph g )`to your graph class and using it as the post-condition for`MST`is the best approach.You can then simply run the

`MST`method on a number of carefully chosen graphs and if the post-condition assertion is never raised (except perhaps for deliberate error inputs, such as disjoint graphs which don't have a spanning tree at all!) then you can assert that your function is producing a spanning tree at least!- Proving that a spanning tree is produced
#### Complexity of MST

Incredibly, quite a number of people started their experiments with a faulty hypothesis. There is no excuse for this - the correct expression can be found in any one of a number of texts. It's also in the PLDS210 notes on the Web.

Table of Contents

© John Morris, 1996