A new train company has decided that they would like to build a super fast train to connect as many of the major US cities as possible. MST can help solve this problem. Minimum Spanning Tree (MST) can keep each city connected, but spend the least amount of money building the tracks. In this homework, you will use Prim's algorithm to build the minimum spanning tree. please create the project called MST. This project has two files: Graph.java and Driver.java Graph.java import java.text.NumberFormat; import java.util.*; public class Graph { //NumberFormat class provides the interface for formatting and parsing numbers. public NumberFormat fmt = NumberFormat.getCurrencyInstance(); //This is adjacency matrix to represent the graph private int [][ ] adjMatrix; //citynames represents vertices in the graph private String[] citynames; //size is number of vertices in the graph private int size; // Constructor. Takes a String array of city names as parameter. // the initial value of weight for each edge in adjMatrix is set to Integer.MAX VALUE public Graph(String[ ] citylist) { //please fill in the body // addEdge method add edge to graph. //given two endpoints and the weight of the edge, you will add the edge to the graph. // You can assume that the graph is undirected. public void addEdge(int c1, int c2, int weight) { //please fill in the body } //// Build the MST from vertex 0. public int prims() { return prims (0); } // prims build the MST from given vertex start. //// prims returns the minimum cost it would require to build the necessary tracks to //// prims build the MST recursively. The parameter is ArrayList visited // it return the total weight of this MST. //// this is the method who does the real work private int prims(ArrayList visited) { //please fill in the body } // This is overloaded addEdge method. //The parameters are 2 strings which represent the end vertices, and // weight represents weight of the edge public void addEdge(String c1, String c2, int weight) { //please fill in the body } // this is overloaded prims method // Given a string representing the vertex, build the MST and return the total // weight. public int prims(String cityname) { //please fill in the body } } //end of graph class driver.java import java.text.NumberFormat; public class Driver { public static void main(String[] args) { //build the graph Graph g = buildGraph(); //call prims() to build MST starting from vertex 0 int cost = g.prims() * 1000; NumberFormat fmt = NumberFormat.getCurrencyInstance(); //print total cost System.out.println("Total Cost: " + fmt.format(cost)); } //end of main method //buildGraph will build the graph provided in the homework private static Graph buildGraph() { //buildGraph will build the graph provided in the homework private static Graph buildGraph() { //names is array of Cityname String names []={"Seattle", "San Francisco", "Las Vegas", "Los Angeles",
