Search code examples
graphdepth-first-searchminimum-spanning-tree

Travelling salesman query

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?

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