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
- adjacency matrix — A graph representation as a V-by-V grid in which the cell at row i, column j records whether, or with what weight, an edge runs from vertex i to vertex j.
- sparse graph — A graph with far fewer edges than the maximum possible, closer to V than to V squared.
- graph — A set of vertices (points) connected by edges (links), used to model networks such as roads, friendships or dependencies.
Taught in
- Representing A Graph: Matrix Or Adjacency List — Algorithms & Data Structures for Working Engineers