Java Reference
In-Depth Information
0
1
2
3
4
0
2
0
1
1
1
1
1
1
4
2
1
1
3
1
1
1
3
4
1
1
1
(A)
(B)
0
1
4
1
0
3
4
2
3
4
3
1
2
4
0
1
2
(C)
Figure11.4
Using the graph representations for undirected graphs. (a) An undi-
rected graph. (b) The adjacency matrix for the graph of (a). (c) The adjacency list
for the graph of (a).
information stored for an edge is one bit to indicate its existence. As the graph be-
comes denser, the adjacency matrix becomes relatively more space efficient. Sparse
graphs are likely to have their adjacency list representation be more space efficient.
Example11.2
Assume that a vertex index requires two bytes, a pointer
requires four bytes, and an edge weight requires two bytes. Then the adja-
cency matrix for the graph of Figure 11.3 requires 2jV
2
j = 50 bytes while
the adjacency list requires 4jVj + 6jEj = 56 bytes. For the graph of Fig-
ure 11.4, the adjacency matrix requires the same space as before, while the
adjacency list requires 4jVj + 6jEj = 92 bytes (because there are now 12
edges instead of 6).
The adjacency matrix often requires a higher asymptotic cost for an algorithm
than would result if the adjacency list were used. The reason is that it is common
for a graph algorithm to visit each neighbor of each vertex. Using the adjacency list,
only the actual edges connecting a vertex to its neighbors are examined. However,
the adjacency matrix must look at each of its jVj potential edges, yielding a total
cost of (jV
2
j) time when the algorithm might otherwise require only (jVj+jEj)
