WEIGHTED GRAPHS AND APPLICATIONS - Introduction to Java Programming: Comprehensive Version - page 1092

an edge ( u , v ), it also has an edge ( v , u ). Only one edge is represented in the
file. When you construct a graph, both edges need to be added.

Your program should prompt the user to enter the name of the file, read data from the
file, create an instance g of WeightedGraph , invoke g.printWeightedEdges()
to display all edges, invoke getMinimumSpanningTree() to obtain an instance
tree of WeightedGraph.MST , invoke tree.getTotalWeight() to display the
weight of the minimum spanning tree, and invoke tree.printTree() to display
the tree. Here is a sample run of the program:

Enter a file name: c:\exercise\WeightedGraphSample.txt
The number of vertices is 6
Vertex 0: (0, 2, 3) (0, 1, 100)
Vertex 1: (1, 3, 20) (1, 0, 100)
Vertex 2: (2, 4, 2) (2, 3, 40) (2, 0, 3)
Vertex 3: (3, 4, 5) (3, 5, 5) (3, 1, 20) (3, 2, 40)
Vertex 4: (4, 2, 2) (4, 3, 5) (4, 5, 9)
Vertex 5: (5, 3, 5) (5, 4, 9)
Total weight in MST is 35
Root is: 0
Edges: (3, 1) (0, 2) (4, 3) (2, 4) (3, 5)

( Hint : Use new WeightedGraph(list, numberOfVertices) to create
a graph, where list contains a list of WeightedEdge objects. Use new
WeightedEdge(u, v, w) to create an edge. Read the first line to get the number
of vertices. Read each subsequent line into a string s and use s.split("[\\|]")
to extract the triplets. For each triplet, use triplet.split("[,]") to extract
vertices and weight.)

*29.10

( Create a file for a graph ) Modify Listing 29.3, TestWeightedGraph.java,
to create a file for representing graph1 . The file format is described in
Programming Exercise 29.9. Create the file from the array defined in lines 7-24
in Listing 29.3. The number of vertices for the graph is 12 , which will be stored
in the first line of the file. An edge ( u , v ) is stored if u < v . The contents of the
file should be as follows:

12
0, 1, 807 | 0, 3, 1331 | 0, 5, 2097
1, 2, 381 | 1, 3, 1267
2, 3, 1015 | 2, 4, 1663 | 2, 10, 1435
3, 4, 599 | 3, 5, 1003
4, 5, 533 | 4, 7, 1260 | 4, 8, 864 | 4, 10, 496
5, 6, 983 | 5, 7, 787
6, 7, 214
7, 8, 888
8, 9, 661 | 8, 10, 781 | 8, 11, 810
9, 11, 1187
10, 11, 239

*29.11

( Find shortest paths ) Write a program that reads a connected graph from a file.
The graph is stored in a file using the same format specified in Programming
Exercise 29.9. Your program should prompt the user to enter the name of
the file then two vertices, and should display a shortest path between the two