**Q:** In the implementations
presented for computing minimum spanning trees and shortest paths,
weighted graphs are represented by storing the weights of edges in the
graphs themselves. What is an alternative to this?

**A:** For graphs containing edges
weighted by factors that do not change frequently, the approach used
in this chapter works well. However, a more general way to think of an
edge’s weight is as a function *w*
(*u*, *v*), where
*u* and *v* are the vertices
that define the edge to which the weight function applies. To
determine the weight of an edge, we simply call the function as
needed. An advantage to this approach is that it lets us compute
weights dynamically in applications where we expect weights to change
frequently. On the other hand, a disadvantage is that if the weight
function is complicated, it may be inefficient to compute over and
over again.

**Q:** When solving the
traveling-salesman problem, we saw that computing an optimal tour is
intractable except when the tour contains very few points. Thus, an
approximation algorithm based on the nearest-neighbor heuristic was
used. What is another way to approximate a traveling-salesman tour?
What is the running time of the approach? How close does the approach
come to an optimal tour?

**A:** Another approach to solving
the traveling-salesman problem using an approximation algorithm is to
compute a minimum spanning tree, then traverse the tree using a
preorder traversal (see Chapter
9). The running time of this approach ...

Start Free Trial

No credit card required