Assignment #6: Minimum Spanning Tree

You are to find the minimum spanning tree for a graph that consists of 128 cities. Here is a map showing the cities. In the "graph", each pair of cities is connected by an undirected edge representing the number of miles between the cities. The minimum spanning tree for this graph will represent 127 roads between cities that allow all cities to be connected to each other. There are many such sets of 127 roads (spanning trees); you are to find the set that uses the minimum asphalt (hence, minimum spanning tree).

The complete data set is in miles.dat. The format of the data file is as follows:

1. The first four lines are commentary.
2. Each of the 128 cities is represented as:
   1. The name of the city (with state), on a separate line. You can ignore everything after the opening brace (those numbers represent latitute, longitute, and maybe population).
   2. A series of zero or more lines, that contains the distance, in miles, to each of the previous cities in the list, in the reverse order of those cities.
3. The last line is a comment also.

Algorithm

Your output should give the total cost of the minimum spanning tree and then list the (127) edges in the minimum spanning tree.

In writing your code, you may assume that the data file is formatted as described above, but you may not assume a limit of 128 cities. The number of cities will not be known until you have finished reading the file. Needless to say, you may only read the file once. So, I would expect that you will need to use some form of a List rather than an arrays or matrices.

Due Date

Submission Procedure