To solve the traveling-salesman problem, we begin with a
graph that is represented simply as a list of vertices. In this
representation, an edge connecting every pair of vertices is implied.
Each vertex in the list is a * TspVertex*
structure (see Example
16.5). This structure consists of four members:

`data`

`x`

`y`

`color`

The *tsp* operation begins by coloring every
vertex white, except the start vertex, which is colored black and
added to the tour immediately. The coordinates of the start vertex are
also recorded so that we can compute distances between it and every
other vertex during the first iteration of the main loop. In the main
loop, we add all of the remaining vertices to the tour. During each
iteration, we look for the white vertex closest to the last vertex.
Each time we add a vertex, we record its coordinates for the next
iteration and color the vertex black. After the loop terminates, we
add the start vertex again to complete the tour.

The runtime complexity of *tsp* is
*O (V* ^{2}), where
*V* is the number of vertices to visit in the tour.
This is because for each of the *V* - 1 iterations
of the main loop, we search the vertices in the graph to determine
which is white and needs a distance computed to it. Notice that
*O (V* ^{2}) is quite an improvement over the runtime complexity for computing an optimal ...

Start Free Trial

No credit card required