Graph Implementations - Data Structures and Abstractions with Java - page 760

FIGURE 29-2

Adjacency lists for the directed graph in Figure 29-1a

Adjacency
lists

Vertices

B
D
E

A

B

E

C

B

D

G

F
H

E

C
H

F

G

H

H I

I F

Question 2 What adjacency lists represent the graph described in Question 1?

Vertices and Edges

29.4

While designing a class that implements the ADT graph, we encounter two other types of objects,
the vertex and the edge. These objects are interrelated: A vertex has edges that leave it, and an edge
is defined by the vertices at its ends.
A vertex in a graph is somewhat like a node in a tree. Both vertices and nodes are implementa-
tion details that we hide from the client. In the implementation of a binary tree, we used a package-
friendly class BinaryNode . (See Segment 24.3 of Chapter 24.) Here, a graph will have package
access to the class Vertex . Previously, we simplified the implementation of a binary tree by giving