In this problem you are to find the minimum spanning tree for a graph that consists of 128 cities. The file cities.pdf 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 miles.dat file. The format of the data file is as follows:

The first four lines are commentary.

Each of the 128 cities is represented as:

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).

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.

The last line is a comment also.

Algorithm:

You can use either Prims or Kruskals 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) *** Implement your code in Java or C/C++. 

cities.pdf

Winnipeg, MB Vancouver, BC Williston, ND Seattle, WA Spokane, WA Tacoma, WA natehee, WA Valley City, ND Sault Sainte Marie, MI Yakima, WA Walla Walla, WA Saint Cloud, MN Rhinelander, WI Sheridan, WY Saint Paul, MN Wausau, WI Watertown, SD. . Traverse City, MI Saint Johnebury, VT Salem, OR Rochester, MN Stevens Point, WI Toronto, ON Watertown, NY Sioux Falls, SD isconsin Dells, WI Rutland, VT Yankton, SD. Waterloo, IA Waukegan, LSaint Joseph, MI Warren Utica, NY Saginaw, MI Rocheeter, NY. Twin Falle, ID Syracuse, NY Schenectady, NY Scottabluff, NB Sioux City, IA Rockford, IL Worcester, MA Toledo, OH Weed, CA .PA Seranton, Springfield, MA South Bend, IN ort..PA Waterbury. CT Rock Springs, WY Sandusky, WilliaSera PA OH Reading, PA PA Wilmington, DE Ravenna, OH Youngetown, Stroudaburg, PA Steubenville, OH Sterling, Co Red Bluff, CA Salt Lake City, UT Uniontown,Trenon, NJ Saint Joseph, Mo, Springfield, IL. Springfield, oH Wheeling Reno, NV Richmond,w Terre Haute, I Sacramento, CA Salida, CO Salina, KS Winehester, . Washington, DC Santa Rosa, CA Richfield, UT Sedalia, MO Saint Louis incenne, IN Salisbury CA Williameon, Staunton, VA Roanoke, VA Stockton, San Francisco, CA Wichita, KS Richmond, VA San Jos, CA Trinidad, co SP pringfield, MO Salinas, CA Tulsa, OK Winston-Salem, NC Santa Fe, NM Rocky Mount, NC Seminole, OK Santa Barbara, CA Tupelo, MS Wilmington, NC San Bernardino, CA Wichita Falls, TX Santa Ana, CA Sumter, SC Texarkana, Shreveport, LA Sherman, TX TX Tu8calooea, AL Roswell, NM Swaineboro, GA San Diego, CA Tyler, TX. Savannah, GA Tuceon, AZ Vicksburg, MS Selma, AL n Angelo, TX. Waycross, GA ta, GA Saint Augustine, FL Waco, TX Tallahaesee, FL San Antonio, Tx. Vietoria, TX Tampa, FL Sarasota, FL Weat Palm Beach, FI