liveBook · Manning

Adjacency list

As explained in Algorithms Every Programmer Should Know

An adjacency list is a graph representation that stores each vertex together with a collection of its neighboring vertices.

An adjacency list represents a graph as a key-value structure: each vertex is a key, and its value is a list of the vertices it connects to. It stores only actual neighbors. section 1.4.5

How the list records connections depends on the graph:

  • For an undirected connection between A and B, include B in A’s list and A in B’s. section 1.4.5
  • For a directed connection, record the neighbor in the direction of the edge; the connection need not be mutual. section 1.4.5
Figure 1.12 The two primary data structures for graph traversals. Left: Simple graph representation with four nodes connected to each other. Middle: An adjacency matrix maps connections from one node to another, denoting them by the value 1 in the matrix and otherwise 0. Right: An adjacency list showing a key-value dictionary connecting to neighboring nodes only.

Compare an adjacency list with an adjacency matrix and see how each represents the same graph. section 1.4.5

How Algorithms Every Programmer Should Know covers it

How deep it goes
Defines the key-value structure and contrasts it with a matrix, without quantifying its space use.
Examples
Uses social following to illustrate one-way edges and friendship to illustrate mutual connections.
What you can do after
Build it from scratch by mapping each vertex to a list of its neighbors.
How it connects
Connects graph representation to adjacency matrices, directed and undirected graphs, and graph traversal.

Also explained in

Compare how 6 books explain adjacency list →

Related concepts

This explainer was generated by Manning's knowledge graph from the text of Algorithms Every Programmer Should Know. The section links point to the parts of the book it draws on.