The Travelling Salesman Problem asks for the cheapest tour that visits every city exactly once and returns home. Finding the exact answer is NP-hard, so in interviews the real skill is producing a good approximation with a provable guarantee. The MST-based method gives a tour that is never worse than twice the optimal — and it is beautifully simple.
Problem. Given a set of cities and the distances between every pair (a metric graph — distances satisfy the triangle inequality), return a tour that visits every city once and comes back to the start, with total cost at most twice the optimal tour.
Example: cities A, B, C, D, E. The method returns the tour A → B → C → D → E → A, guaranteed to be at
most 2× the best possible tour.
The slow way first
The brute-force tour tries every ordering of the cities. With n cities there are (n - 1)! / 2 distinct tours — that is O(n!), hopeless beyond a dozen cities. Even the best exact algorithm (Held–Karp dynamic programming) is O(n² · 2ⁿ), still exponential.
So we change the question: instead of the best tour, can we cheaply build a tour that is provably close to the best? Yes — and the key is an object we already know how to compute fast: a minimum spanning tree.
The idea: walk a minimum spanning tree
A minimum spanning tree (MST) connects all cities with the cheapest set of edges that forms no cycle. Its total weight is a lower bound on the optimal tour (deleting one edge from any tour leaves a spanning tree, which costs at least the MST). So MST ≤ OPT.
Now do a preorder depth-first walk of the MST. If you traversed every tree edge twice (down and back up) you would pay 2 · MST. But you do not have to backtrack: when the walk would revisit a city, you shortcut straight to the next unvisited city. Because distances obey the triangle inequality, shortcutting never costs more. So the final tour costs at most 2 · MST ≤ 2 · OPT.
The whole guarantee rests on two facts: MST ≤ OPT, and shortcutting (triangle inequality) only helps. Chain them and you get the 2-approximation.
Walk through it
Step through the animation. First the cheapest tree lights up (the MST, rooted at A). Then a preorder DFS visits A, then its children B, C, D, and D's child E. Each newly reached city is appended to the tour; any city already visited is skipped via a shortcut. Finally we close the loop back to A, giving A → B → C → D → E → A.
Pseudocode
build the minimum spanning tree T of the graph
root T at the start city
tour = empty list, seen = empty set
for each city v in a preorder DFS of T:
if v has not been seen:
mark v seen
append v to tour
append the start city to tour # return home
return tourThe Python solution
def tsp_2approx(graph, start):
# 1) minimum spanning tree of the graph
mst = minimum_spanning_tree(graph)
# 2) preorder DFS walk, shortcutting repeats
tour, seen = [], set()
for v in preorder_dfs(mst, start):
if v not in seen:
seen.add(v)
tour.append(v)
tour.append(start) # return home
return tourminimum_spanning_tree(graph)builds the cheapest cycle-free tree (Prim or Kruskal under the hood).preorder_dfs(mst, start)yields cities in the order a depth-first walk first reaches them.- The
if v not in seencheck is the shortcut: a city already in the tour is skipped, so we never backtrack. seen.add(v)andtour.append(v)record each city the first time we see it.tour.append(start)closes the loop, turning the walk into a proper Hamiltonian tour.
Complexity
| Case | Time | Notes |
|---|---|---|
| Exact (brute force) | O(n!) (slow) | every ordering of cities |
| Exact (Held-Karp DP) | O(n² · 2ⁿ) (moderate) | still exponential |
| MST 2-approximation | O(E log V) (moderate) | dominated by building the MST |
O(V + E) (moderate)Building the MST (Prim with a heap, or Kruskal) costs O(E log V); the DFS walk is linear. We trade a tiny bit of optimality for a polynomial-time algorithm with a hard guarantee: cost ≤ 2 × optimal.
When this pattern shows up
When an exact answer is NP-hard, interviewers often want an approximation with a proof. The pattern here — bound the optimum by a structure you can compute fast (the MST), then transform it without adding cost (shortcutting via the triangle inequality) — recurs across approximation algorithms. Christofides refines the same idea to a 1.5× bound by adding a matching.
The 2× guarantee needs the triangle inequality (a metric graph). If distances can violate it — a detour through a third city is cheaper than the direct edge — shortcutting can make the tour worse, and the bound no longer holds. Always confirm the metric assumption before quoting the factor.
Practice
The MST of a graph has total weight 40. Without computing the exact tour, what can you say about the optimal TSP tour cost, and the cost of the tour this method returns?
1. Why is the MST weight a lower bound on the optimal tour?
2. What does the shortcut step rely on to avoid increasing the cost?
3. What is the approximation factor of this method on a metric graph?
4. What dominates the running time of the algorithm?