Java Reference
In-Depth Information
C
HAPTER
S
UMMARY
•
An adjacency list for a given vertex contains references to the vertex's neighbors.
•
Using an adjacency list, you can quickly find all the neighbors of a particular vertex. But if you want to
know whether an edge exists between any two given vertices, you need to search a list.
•
An adjacency matrix is a two-dimensional array that represents the edges in a graph. If you number the ver-
tices from 0 through
n
-
1, the entry in row
i
and column
j
of the matrix indicates whether an edge exists
between vertex
i
and vertex
j
. For an unweighted graph, you can use boolean values in the matrix. For a
weighted graph, you can use edge weights when edges exist and a representation of infinity otherwise.
•
Using an adjacency matrix, you can quickly discover whether an edge exists between any two given verti-
ces. But if you want to know all the neighbors of a particular vertex, you need to scan an entire row of the
matrix.
•
Each adjacency list represents only those edges that originate from a vertex, but an adjacency matrix
reserves space for every possible edge in a graph. Thus, when a graph is sparse, adjacency lists use less
memory than a corresponding adjacency matrix. For this reason, typical graph implementations use adja-
cency lists.
•
One way to implement an adjacency list is to make it a data field of a class
Vertex
. So that you can represent
weighted graphs as well as unweighted graphs, you place instances of a class
Edge
in the adjacency list.
Edge
's data fields include the terminal vertex of an edge and the edge weight.
Vertex
is accessed from
within a package instead of publicly.
Edge
is an inner class of
Vertex
. Thus, both
Vertex
and
Edge
are hid-
den from the graph's client.
•
To facilitate the implementation of various graph algorithms, an instance of the class
Vertex
can indicate
whether it has been visited. It also can record data about a path to it, such as the previous vertex and the
path's cost.
E
XERCISES
1.
What adjacency matrix represents the graph in Figure 28-15a of the previous chapter?
2.
What adjacency matrix represents the graph in Figure 28-18a of the previous chapter?
3.
What adjacency lists represent the graph in Figure 28-15a of the previous chapter?
4.
What adjacency lists represent the graph in Figure 28-18a of the previous chapter?
5.
When is an adjacency matrix just as space-efficient as adjacency lists?
6.
Suppose that you want only to test whether an edge exists between two particular vertices. Does an adjacency
matrix or an adjacency list provide a more efficient way of doing this?
7.
Suppose that you want only to find all vertices that are adjacent to some particular vertex. Does an adjacency
matrix or an adjacency list provide a more efficient way of doing this?
8.
Complete the implementation of the class
Vertex
that was begun in Segment 29.11.
9.
What is the Big Oh of the methods
getBreadthFirstTraversal
and
getShortestPath
, as given in
Segments 29.23 and 29.24?
