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.
Covers
Graphs algorithms, binary heaps, disjoint sets, more Java programming.
Graph details
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:
- The first four lines are commentary.
- Each of the 128 cities is represented as:
- 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).
- 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.
- The last line is a comment also.
Algorithm
The algorithm you will use is Kruskal's algorithm (Chapter 24).
Because the Collections API does not include a disjoint sets data
structures,
which is esssential for an efficient implementation,
you may and should use the
DisjointSets implementation
from the textbook. It is in package
weiss.nonstandard.
You must also use
the PriorityQueue
implementation in java.util to allow selection
of edges by order of weight, and
you must initialize the binary heap using the
linear-time heap construction constructor.
You may also use any class in java.util that you deem appropriate.
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.
Submission Procedure
Submit all your source code, and the results of running the program
on the test case.