Page 73 - Data Structures Interactive Book
P. 73
8.2.2 Adjacency List
An adjacency list represents the graph as an array (or vector) of lists. Each list
corresponds to a vertex and contains all the vertices that are directly connected to it. This
representation is more space-efficient for sparse graphs, as it only stores existing edges rather
than all possible connections.
Adjacency lists are widely used in practice because they reduce memory usage and
make traversal operations like BFS and DFS more efficient. However, checking whether two
vertices are directly connected may take longer compared to adjacency matrices, since it
requires searching through a list.
Example: Adjacency List in C++
This program builds the same graph as before but uses an adjacency list. The output
shows each vertex followed by the list of vertices it connects to, making the structure easy to
understand.
73
