2-Approximation TOTAL POINTS 1 1 2 1. Implement an approximation algorithm for the Traveling Salesman problem, which outputs a solution which is a 2. approximation of the optimal weight. 1 import networkx as nx 3 # This function takes as input a graph g. # The graph is complete (i.e., each pair of distinct vertices is connected by an edge), # undirected (i.e., the edge from u to v has the same weight as the edge from v to u), # and has no self-loops (i.e., there are no edges from i to i). # The function should return a 2-approximation of an optimal Hamiltonian cycle. 4 5 6 7 # 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 def approximation(g): #n is the number of vertices. n = g. number_of_nodes() # You might want to use the function "nx.minimum_spanning_tree (g)" # which returns a Minimum Spanning Tree of the graph g # You also might want to use the command "list(nx.dfs_preorder_nodes (graph, e))" # which gives a list of vertices of the given graph in depth-first preorder. return ??? Run Reset