Adjacency List

An adjacency list stores, for each vertex, the vertices connected to it.

It is the most common graph representation in Python algorithm practice because it is compact and easy to traverse.

Core Idea

The algorithm looks up a vertex and iterates through its neighbors. This fits BFS, DFS, connected components, and many shortest path algorithms.

For sparse graphs, where each vertex has only a few edges compared with all possible edges, an adjacency list saves memory.

Python Example

graph = {
    0: [1, 2],
    1: [0, 3],
    2: [0],
    3: [1],
}
 
for neighbor in graph[0]:
    print(neighbor)

The loop visits the neighbors of vertex 0.

Common Confusions

For an undirected graph, each edge usually appears twice: once in each endpoint’s neighbor list.

For a weighted graph, each neighbor entry must also include the weight, such as (neighbor, cost).

When To Use It

Use an adjacency list when the algorithm repeatedly asks “where can I go from this vertex?” and the graph is not so dense that a matrix would be simpler.