Since T is implemented using a list in the getMinimumSpanningTree and getShortestPath methods in Listing 29.2 WeightedGraph.java, testing whether a vertex u is in T by invoking T.contains(u) takes O(n) time. Modify these two methods by introducing an array named isInT. Set isInT[u] to true when a vertex u is added to T. Testing whether a vertex u is in T can now be done in O(1) time. Write a test program using the following code, where graph1 is created from Figure 29.1.

Listing

WeightedGraph graph1 = new WeightedGraph (edges, vertices); WeightedGraph .MST treel = graph1.getMinimumSpanningTree(); + treel.getTotalWeight()); System.out.println("Total weight is " treel.printTree(); WeightedGraph .ShortestPathTree tree2 = graph1.getShortestPath(graph1.getIndex("Chicago")); %3D tree2.printA11Paths (); 1 import java.util.*; 2 3 public class WeightedGraph extends AbstractGraph { 4 /** Construct an empty */ public WeightedGraph() { /** Construct a WeightedGraph from vertices and edged in arrays */ public WeightedGraph(V[] vertices, int[][] edges) { 10 11 12 createWeightedGraph(java.util.Arrays.asList(vertices), edges); 13 /** Construct a WeightedGraph from vertices and edges in list */ public WeightedGraph(int[][] edges, int numberofVertices) { 14 15 16 17 18 19 20 21 List vertices = new ArrayList (); for (int i = 0; i < numberofVertices; i++) vertices.add((V) (new Integer(i))); createWeightedGraph(vertices, edges);