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

AbstractGraph.Edge is an inner class defined in the AbstractGraph class. It represents
an edge from vertex u to v . WeightedEdge extends AbstractGraph.Edge with a new
property weight .
To create a WeightedEdge object, use new WeightedEdge(i, j, w) , where w is the
weight on edge ( i , j ). Often you need to compare the weights of the edges. For this reason,
the WeightedEdge class implements the Comparable interface.
For unweighted graphs, we use adjacency lists to represent edges. For weighted graphs, we
still use adjacency lists, the adjacency lists for the vertices in the graph in Figure 29.3a can be
represented as follows:

java.util.List<WeightedEdge>[] list = new java.util.List[ 5 ];

list[0]
list[1]

WeightedEdge(0, 1, 2) WeightedEdge(0, 3, 8)

WeightedEdge(1, 0, 2) WeightedEdge(1, 2, 3) WeightedEdge(1, 2, 7)

list[2]

WeightedEdge(2, 3, 4) WeightedEdge(2, 4, 5) WeightedEdge(2, 1, 7)

list[3]
list[4]

WeightedEdge(3, 1, 3) WeightedEdge(3, 2, 4) WeightedEdge(3, 4, 6) WeightedEdge(3, 0, 8)

WeightedEdge(4, 2, 5) WeightedEdge(4, 3, 6)

list[i] stores all edges adjacent to vertex i .
For flexibility, we will use an array list rather than a fixed-sized array to represent list
as follows:

List<List<WeightedEdge>> list = new java.util.ArrayList<>();

29.1

✓ ✓

For the code WeightedEdge edge = new WeightedEdge(1, 2, 3.5) , what is
edge.u , edge.v , and edge.weight ?

Check

Point

29.2

What is the output of the following code?

List<WeightedEdge> list = new ArrayList<>();
list.add( new WeightedEdge( 1 , 2 , 3.5 ));
list.add( new WeightedEdge( 2 , 3 , 4.5 ));
WeightedEdge e = java.util.Collections.max(list);
System.out.println(e.u);
System.out.println(e.v);
System.out.println(e.weight);

29.3 The WeightedGraph Class
The WeightedGraph class extends AbstractGraph .

Key
Point

The preceding chapter designed the Graph interface, the AbstractGraph class, and
the UnweightedGraph class for modeling graphs. Following this pattern, we design
WeightedGraph as a subclass of AbstractGraph , as shown in Figure 29.4.
WeightedGraph simply extends AbstractGraph with five constructors for creating con-
crete WeightedGraph instances. WeightedGraph inherits all methods from AbstractGraph ,
overrides the clear and addVertex methods, implements a new addEdge method for add-
ing a weighted edge, and also introduces new methods for obtaining minimum spanning trees
and for finding all single-source shortest paths. Minimum spanning trees and shortest paths will
be introduced in Sections 29.4 and 29.5, respectively.
Listing 29.2 implements WeightedGraph . Edge adjacency lists (lines 38-63) are used
internally to store adjacent edges for a vertex. When a WeightedGraph is constructed, its edge