Problem 3 CMPS109

Due: 11:59 pm.- Feb 5, 2003 Ira Pohl

OORedo class graph and MST using STL in C++

OO Programs should rely as much as possible on standard components. We will improve on problem 2 - using STL in C++. You are to reimplement your code for problem 2 using C++ and relying on the standard library and the containers in STL as much as possible. You should include a method that computes the minimum spanning tree or forest for this graph. You should include methods that print out the graph as well as the edge cost of the MST. The preferred method for implementing MST is Prim's algorithm. This was described in class. It should be familiar from earlier courses in your curriculum. It is found in Baase and VanGelder which is on reserve. In Prim you should use a priority queue to select the next smallest edge. STL has such a container. Also STL has vector and list that should be convenient for the basic representation of your graph. Again consult with the TA in lab on pointers for using STL. If problem 2 was already working this should be a relatively easy translation.

Test your graph methods including MST on values: 10, 100, 1000 for vertex size, and .2, .33, and .4 density.

The teaching assistant Mark Slater will provide further advice on how to code this

problem in good style.