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.

Function Contract

build_graph(n, edges) expects vertices numbered from 0 through n - 1 and edges as pairs (a, b).

It returns a list of neighbor lists. Because the example builds an undirected graph, each edge is stored twice, once from a to b and once from b to a.

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.

Building from Edges

For an undirected graph:

def build_graph(n, edges):
    graph = [[] for _ in range(n)]
 
    for a, b in edges:
        graph[a].append(b)
        graph[b].append(a)
 
    return graph

For a directed graph, add only graph[a].append(b).

Weighted Version

For weighted edges, store the weight with the neighbor:

graph[a].append((b, weight))

Then traversal code must unpack both values.

Complexity

An adjacency list uses O(V + E) space. Traversing all vertices and all adjacency lists costs O(V + E).

Checking whether a specific edge exists may require scanning one vertex’s neighbor list unless another structure is added.

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).

Another common mistake is creating adjacency lists only for vertices that appear in edges. If isolated vertices matter, they still need entries.

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.

It is the default representation for most BFS, DFS, shortest path, and component problems in Python.

The Main Point

An adjacency list is the default Python graph representation when traversal asks, for each vertex, which neighbors can be reached next.