Java Reference
In-Depth Information
0
1
2
3
4
0
2
0
1
1
1
1
4
2
1
3
1
1
3
4
1
(A)
(B)
0
1
4
1
3
2
4
3
2
4
1
(C)
Figure11.3
Two graph representations. (a) A directed graph. (b) The adjacency
matrix for the graph of (a). (c) The adjacency list for the graph of (a).
to Vertex 1 and one going to Vertex 4. The list for Vertex 2 stores an entry
for Vertex 4 because there is an edge from Vertex 2 to Vertex 4, but no entry
for Vertex 3 because this edge comes into Vertex 2 rather than going out.
The storage requirements for the adjacency list depend on both the number of
edges and the number of vertices in the graph. There must be an array entry for
each vertex (even if the vertex is not adjacent to any other vertex and thus has no
elements on its linked list), and each edge must appear on one of the lists. Thus,
the cost is (jVj + jEj).
Both the adjacency matrix and the adjacency list can be used to store directed
or undirected graphs. Each edge of an undirected graph connecting Vertices U
and V is represented by two directed edges: one from U to V and one from V to
U. Figure 11.4 illustrates the use of the adjacency matrix and the adjacency list for
undirected graphs.
Which graph representation is more space efficient depends on the number of
edges in the graph. The adjacency list stores information only for those edges that
actually appear in the graph, while the adjacency matrix requires space for each
potential edge, whether it exists or not. However, the adjacency matrix requires
no overhead for pointers, which can be a substantial cost, especially if the only
