CSCI 311 - Program 3

Graphs - Prim's Algorithm for finding aMinimal Spanning Tree

Dr. Melody Stapleton, Instructor

Shaun McCluskey Teaching Assistant

Due Date:

• All Program Components: Friday, May 23 - Last day of Final's Week - by MIDNIGHT!!!!

Shaun will provide the final input file(s) to run your program against.

******************************************************************************

Your assignment is to program the Prim's minimal spanning tree algorithm in a fashion similar to that shown
on page 592 of Kruse's Chapter 12 on graphs (pages 23 and 24 in the Chapter 12 online notes) , but with some
required modifications. The code on page 592 (pages 23-24 of online notes) works with an adjacency table implementation
of an undirected graph also know as just a graph or network. You will be using the c++ STL(standard template library)
to implement the network. All students will be required to use the map class to create the adjacency table.
Use the ideas for implementation of a graph (aka network) that is not a digraph on P. 590 of Kruse. In an undirected graph (graph or network) one must be sure that if there is an edge from x to y of weight w, there is also represented
an edge from y to x of weight w. I.e., the graph is symmetric.

You are to create a class "network" that will have a number of methods. At the minimum it will have a constructor, destructor and a method to "read" in the relevant values to build the internal "mixed" representation of the graph. Your input file format is specified below. You will also need to build a method that "prints" the graph, and prints it in a way that looks like the picture on page 576, Figure c) (page 7 of the online notes, Figure c)). I.e., you will print across a row, first the "from vertex" of an edge and then next to it print the list of "to" (or adjacent) vertices for that vertex. Your first row will be for the "from" vertex A, second row for the "from" vertex B, etc.

Your "read' method for the graph class needs to process files in the following format:

• [stringA] [stringB] [5] //specifies there is an edge from stringA to stringB of weight 5 in the graph
• [StringC] [stringD] [10] //specifies there is an edge from stringC to stringD of weight 10 in the graph
• [stringB] // source vertex

Example:

As soon as you have read in and processed all the edges of the graph, you need to then call your "print" method to print out the graph as described above.

Next, process the request to find the minimal spanning tree associated with the source vertex. Once you have found the minimal spanning tree, which is constructed as a network, print out the minimum spanning tree with the same print routine you used to print out your original graph.

You will have at least 4 such weighted graph files to process with your program.