When a graph stores every edge in one list, finding a vertex’s neighbors requires scanning that list. An adjacency list instead maps each vertex to its incident or outgoing edges, making graph operations depend on local neighborhoods. section 14.1.1
A directed graph
A compact representation maps 1 to edges leading to 2 and 3, maps 2 to an edge leading to 4, and gives 3 and 4 empty lists. Each entry can store an edge object containing its source, destination, weight, and label. section 14.1.1 section 14.1.3
A practical graph implementation typically provides:
- A vertex collection plus a hash-table mapping each vertex to its edge list. section 14.1.3
- Vertex insertion that initializes an empty list, and edge insertion that validates endpoints and replaces an existing edge when necessary. section 14.1.3
- Space usage of O(|E| + |V|); listing outgoing or incoming edges costs O(|E|), while a dense graph may favor an adjacency matrix. section 14.6
1 -> [(1,2), (1,3)] 2 -> [(2,4)] 3 -> [] 4 -> []
Browse a concrete adjacency-list mapping before comparing it with the corresponding matrix representation. section 14.1.1
