You should also provide a constructor that builds random graphs. The parameters should be an integer representing the number of vertices, a Random object, and another integer, and the constructor should fill the portion of the adjacency matrix above the main diagonal in row-major order by values chosen randomly and uniformly from 1 through the value of the second integer. It should fill the rest of the matrix by symmetry. All entries on the main diagonal should be zero.

For the kruskal method, you will need an Edge class, a PriorityQueue class and a DisjSet. You may replace the SetType and Vertex classes by int. You may replace the DisjSet class by the DisjSetsFast class, available from the author's web site. You may use your own priority queue, mine, or the text's (giving credit as appropriate). You will have to provide a readGraphIntoHeap() method. If you want, you may incorporate the buildHeap method into it.

Both tspApprox and kruskal should return Vectors of Edges. The traverseEdgeVector method should take such a vector and print a representation of each edge, including source, destination, and weight, to System.out. It should also print the sum of the costs of all the edges in the vector. The traverse method needs only print a representation of the adjacency matrix to System.out. You need not label the rows or columns.

Note that the Edge class will have to implement the Comparable interface if it is used as the element type for the PriorityQueue.

The tspApprox method should compute a greedy approximate solution to the Traveling Salesman Problem of p. 340 of the text. It should work by inspecting the edges of the graph in order of nondecreasing cost (as in Kruskal's algorithm), and including an edge in the output vector iff it does not complete a cycle, and neither endpoint appears more than once in the edges already added to the vector. When n-1 edges have been found, the nth edge is determined and the method may terminate after adding this edge to the output.

Note that this algorithm only works for undirected graphs. The approximation found may not be a very good one. For example, even in the last test case, where n is just 6, it misses the path (0 4 2 1 5 3 0) with cost 9 + 39 + 32 + 2 + 9 + 16 = 107. On the other hand, no efficient algorithm is known for exact solution of the problem.

Use the file A5.java (available on the class web site) to test your implementation.

Late submissions for this assignment must be turned in by 5:30 p.m., Thursday, December 13. As always, there will be a penalty for late submissions.