adjacency list

A graph representation that stores, for each vertex, a list of its neighbours, typically as a dict of lists in Python.

In more detail

It uses O(V + E) memory and lets you loop over a vertex's neighbours in time proportional to how many it has. Checking whether one specific edge exists means scanning a list. It is the usual choice for sparse graphs, which most real graphs are.

Example

graph = {'A': ['B', 'C'], 'B': ['A'], 'C': ['A']}

Related terms

Taught in

References