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

29.2

From an adjacency matrix, you quickly can see whether an edge exists between any two given ver-
tices. This operation is O(1). But if you want to know all the neighbors of a particular vertex, you
need to scan an entire row of the matrix, an O( n ) task. Additionally, the matrix occupies a consider-
able, fixed amount of space that depends on the number of vertices but not on the number of edges.
In fact, an adjacency matrix represents every possible edge in a graph, regardless of whether the
edges actually exist. However, most graphs have relatively few of the many edges possible—that
is, they are sparse. For such graphs, an adjacency list uses less space, as you will now see.

Note: An adjacency matrix uses a fixed amount of space that depends on the number of
vertices, but not the number of edges, in a graph. The adjacency matrix for a sparse graph
wastes space, because the graph has relatively few edges.

Note: Seeing whether an edge exists between any two given vertices of a graph can be
done quickly when you use an adjacency matrix. But you need to scan an entire row of the
matrix if you want to know all the neighbors of a particular vertex.

Question 1 Consider the graph in Figure 28-4b of the previous chapter. Number the verti-
ces from 0 through 3, starting at the vertex in the upper left corner and moving in a clock-
wise direction. What adjacency matrix represents this graph?

The Adjacency List
29.3

An adjacency list for a given vertex represents only those edges that originate from the vertex. In
Figure 29-2, each vertex of the graph in Figure 29-1a references a list of adjacent vertices. Space is
not reserved for edges that do not exist. Thus, the adjacency lists, taken together, use less memory
than the corresponding adjacency matrix in Figure 29-1b. For this reason, implementations of
sparse graphs use adjacency lists. The implementation that we present in this chapter will do so
also, since typical graphs are sparse.
Although the adjacency lists in our diagram contain vertices, they will actually contain
edges in our implementation. Each of these edges, however, will contain the illustrated vertex as
its terminal vertex.

Note: An adjacency list for a given vertex represents only those edges that originate from
the vertex. For a sparse graph, an adjacency list uses less memory than an adjacency matrix.
For a dense graph, an adjacency matrix can be the better choice.

Note: Using adjacency lists, you can find all the neighbors of a particular vertex by travers-
ing a list. If you want to know whether an edge exists between any two given vertices, you
need to search a list. If the graph contains n vertices, each of these operations is O( n ) at worst,
but is faster on average.