Objectives

Add member functions to your graph class to:

• a. Perform and animate a shortest path algorithm
  
• b. Perform and animate a minimal spanning tree algorithm.
  

First

• Complete Graph Data Structure and Algorithms Lab One. You will need the adjacency list data structure that you built to store your graph data.
  
• Run ColorGrapher on several data files for inspiration and to see how the algorithms work.

And then

You are pretty much on your own.

• Read Chapter 31 Weighted Graphs in Sedgewick.
  
• Listen in class. We will discuss these algorithms in detail.
• You will need stack and/or queue data structures to implement these algorithms.
• Additional tips and comments may appear here later in the quarter.

Turn in

• A diskette with soft copy of your code, a working application, and data files.
  
• A readme explaining how to run your program.

Last Updated: April 4, 1999 9:35 am by