Java Reference
In-Depth Information
We now consider how to use
Vertex
in an implementation of a directed graph that can be either
weighted or unweighted.
29.16
Beginning the class.
Whether our implementation uses an adjacency list—as it will here—or an
adjacency matrix, it must have a container for the graph's vertices. If we use integers to identify the
vertices, a list would be a natural choice for this container, since each integer could correspond to a
position within the list. If we use an object such as a string to identify them, a dictionary is a better
choice. That is what we will do here.
Note:
Regardless of the kind of graph or how you implement it, you need a container such
as a dictionary for the graph's vertices.
Figure 29-3 illustrates a dictionary of vertices for a small directed graph. Each of the vertices
A
and
D
has an adjacency list of the edges that originate at that vertex. The letters within these edges represent
references to corresponding vertices within the dictionary. Since the ADT dictionary consists of key-
value pairs, we can use the vertex labels as the search keys and the vertices themselves as the corre-
sponding values. This organization allows us to quickly locate a particular vertex, given its label.
VideoNote
Implementing graph
operations
FIGURE 29-3
(a) A directed graph and (b) its implementation using adjacency lists
(a)
(b)
Dictionary
Vertices
Adjacency lists
A
D
A
Edges
B
C
D
B
C
B
C
D
A
C
Our class begins as shown in Listing 29-5. Recall that the generic type
T
represents the data
type of the objects that label the graph's vertices. The class's first data field is a dictionary of verti-
ces. A count of vertices is not necessary, since the dictionary will count the vertices for us.
Since each vertex maintains its own adjacency list, the edges in the graph are not easily
counted. Thus, we should maintain an edge count as a data field within the graph class.
LISTING 29-5
An outline of the class
DirectedGraph
package
GraphPackage;
import
java.util.Iterator;
import
ADTPackage.*;
// classes that implement various ADTs
