(Test if a vertex u is in T efficiently) 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

(Test if a vertex u is in T efficiently) 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.

FIGURE 29.1 The graph models the distances among the cities.

WeightedGraph<String> graph1 = new WeightedGraph<>(edges, vertices);
WeightedGraph<String>.MST tree1 = graph1.getMinimumSpanningTree();
System.out.println("Total weight is " + tree1.getTotalWeight());
tree1.printTree();
WeightedGraph<String>.ShortestPathTree tree2 = 
 graph1.getShortestPath(graph1.getIndex("Chicago"));
tree2.printAllPaths();