What's the difference between Minimmum Spanning Tree and Travelling Salesman Problems

Question

please be precise.

Answer 1

The Minimum Spanning Tree problem asks you to build a tree that connects all cities and has minimum total weight, while the Travelling Salesman Problem asks you to find a trip that visits all cities with minimum total weight (and possibly coming back to your starting point).

If you're having trouble seeing the difference, in MST, you need to find a minimum weight tree in a weighted graph, while in TSP you need to find a minimum weight path (or cycle / circuit). Does that help?

Answer 2

It's the difference between "Finding an acyclic connected subgraph T of G with V(T) = V(G) and Weight(T) is minimal" and "Finding a cycle C in G such that V(C) = V(G) and Weight(C) is minimal" where Weight(X) = Sum of edges of X.