8.7.2 Traveling Salesman Problem

This assignment involves implementing the following five problems.

1.

Generate a complete graph with n vertices and random costs for all the edges. Let the costs be positive integers uniformly distributed between 1 and 100.

2.

Find a minimum cost spanning tree (MST) for the above graph, using an efficient implementation of Prim's algorithm. Compute the running time of this program.

3.

Find an MST using Kruskal's algorithm. In the implementation, use the partially ordered tree data structure to organize the set of edges and the MFSET data structure to implement union's and find's. Compare the running time with that of Prim's algorithm.

4.

Find a Hamiltonian path using a greedy strategy based on Kruskal's algorithm.

5.

Find an optimal Hamiltonian path for the above graph using the branch and bound methodology.

It should be possible to input any desired graph and carry out steps 2, 3, 4, and 5 above. Assume the following input format: Let the set of vertices beV = {1,..., n}Then the input file would be: n, Cost of edge (1, 2), ..., Cost of edge (1, n), Cost of edge (2, 3), ..., Cost of edge (2, n), Cost of edge (3, 4), ..., Cost of edge (n - 1, n).