Question

I have read that one of the approximations for the TSP is to do the following: - Compute the minimal spanning tree (MST) - Perform a DFS of the MST

The goal of solving the TSP is that every vertex is visited exactly once. A traveler starts at point 'A' and he needs to visit all other points on a graph and come back to point 'A' (some times, this clause is not present) ensuring that each point is visited exactly once.

Assume that the MST 'T' of a graph G is as follows: Minimal spanning tree of a graph

The DFS of this MST is A-B-C-E-D.

My question is for solving the TSP, I need the list of all cities (points) that a traveler must visit. Clearly, there exists no path from 'E' to 'D' in the MST. How does this solve the problem then?

Was it helpful?

Solution

It doesn't matter if there is no path from E to D in the MST as long as there is a path from E to D in the original graph. Usually the TSP involves a completely connected graph.

See section 2.1 of this paper for more info: http://www.cs.tufts.edu/~cowen/advanced/2002/adv-lect3.pdf

Licensed under: CC-BY-SA with attribution
Not affiliated with StackOverflow
scroll top