An adjacency list represents a graph as a key-value structure: each vertex is a key, and its value is a list of the vertices it connects to. It stores only actual neighbors. section 1.4.5
How the list records connections depends on the graph:
- For an undirected connection between A and B, include B in A’s list and A in B’s. section 1.4.5
- For a directed connection, record the neighbor in the direction of the edge; the connection need not be mutual. section 1.4.5
Figure 1.12 The two primary data structures for graph traversals. Left: Simple graph representation with four nodes connected to each other. Middle: An adjacency matrix maps connections from one node to another, denoting them by the value 1 in the matrix and otherwise 0. Right: An adjacency list showing a key-value dictionary connecting to neighboring nodes only.
Compare an adjacency list with an adjacency matrix and see how each represents the same graph. section 1.4.5





