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

vertices. For example, for the graph in Figure 29.23, a shortest path between 0
and 1 can be displayed as 0 2 4 3 1 .

Here is a sample run of the program:

Enter a file name: WeightedGraphSample2.txt
Enter two vertices (integer indexes): 0 1
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)
A path from 0 to 1: 0 2 4 3 1

*29.12

( Display weighted graphs ) Revise GraphView in Listing 28.6 to display a
weighted graph. Write a program that displays the graph in Figure 29.1 as
shown in Figure 29.25. (Instructors may ask students to expand this program
by adding new cities with appropriate edges into the graph).

F IGURE 29.25

Programming Exercise 29.12 displays a weighted graph.

*29.13

( Display shortest paths ) Revise GraphView in Listing 28.6 to display a
weighted graph and a shortest path between the two specified cities, as shown
in Figure 29.19. You need to add a data field path in GraphView . If a path
is not null, the edges in the path are displayed in red. If a city not in the map is
entered, the program displays a text to alert the user.

*29.14

( Display a minimum spanning tree ) Revise GraphView in Listing 28.6
to display a weighted graph and a minimum spanning tree for the graph in
Figure 29.1, as shown in Figure 29.26. The edges in the MST are shown in red.

***29.15

( Dynamic graphs ) Write a program that lets the users create a weighted graph
dynamically. The user can create a vertex by entering its name and location, as
shown in Figure 29.27. The user can also create an edge to connect two verti-
ces. To simplify the program, assume that vertex names are the same as vertex