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:

Data from Listing 29.2,

Transcribed Image Text:

WeightedGraph.ShortestPathTree tree2 = graph1.getShortestPath(graph1.getIndex ("Chicago")): tree2.printA11Paths ():