Use Python to find the minimum spanning tree for a graph

In this problem you are to find the minimum spanning tree for a graph that consists of 128 cities. The file [login to view URL] contains the map of the cities. In the graph, each pair of cities is connected by an undirected edge and its weight is given by the number of miles between the two cities. The minimum spanning tree for this graph will represent 127 roads between cities that allow all cities to be connected to each other. There are many such sets of 127 roads (spanning trees); you are to find the set that uses the minimum asphalt (hence, minimum spanning tree). The complete data set is in the [login to view URL] file. The format of the data file is as follows: 1. The first four lines are commentary. 2. Each of the 128 cities is represented as: 1. The name of the city (with state), on a separate line. You can ignore everything after the opening brace (those numbers represent latitude, longitude, and maybe population). 2. A series of zero or more lines, that contains the distance, in miles, to each of the previous cities in the list, in the reverse order of those cities. 3. The last line is a comment also. Algorithm: You can use either Prim’s or Kruskal’s algorithm. Your output should give the total cost of the minimum spanning tree and then list the (127) edges in the minimum spanning tree, starting with Youngstown, OH. In the following format: Youngstown, OH – Yankton, SD Yankton, SD – Yakima, WA Yakima, WA - ... ... (Note that this example is only for formatting purposes and is not in fact part of the MST) Implementation: Implement your code Python. Name the source file as yourFirstName_yourLastName.py. Provide clear instructions how to use your code. Submission: In your submission PDF document explain the choice of algorithm, and list all the data structures used for implementation. Explain why you used these data structures. Include the resulting output from running your code in the PDF document. Additionally, submit all your source files. Grading: • 10 points for explanation of choice of algorithm and data structures • 10 points for correct program output • 10 points for running program