using c++ only

Minimum Spanning Tree: Solving TSP* for Metric Graphs using MST Heuristic

Given an arbitrary metric graph, construct its Minimum Spanning Tree using Kruskal's algorithm. You can assume adjacency matrix representation of graphs. If you wish, you can reuse external libraries for heaps.

Now use the constructed MST to find an approximate estimate for the TSP problem. You can choose to implement any of the two approximation algorithms specified in Wikipedia's entry on TSP One with approximation factor of 1.5 (Christofides) or 2. Compare it with the optimal answer. You can use some external library to find the optimal solution to the TSP problem.

* TSP: Travel Salesman Problem

using c++ only please