Skip to content
Tutorials Center
My learning

Topics

Lesson 6 of 36 ยท Graphs and Representations

The Adjacency List

Learn the adjacency list, the standard sparse-graph representation: build it with dictionaries and sets in Python, store weights and directions, and compare memory against matrices.

Most real graphs are sparse. A social network with a billion people does not have a billion friendships each. If you stored a billion-by-billion matrix you would waste almost all of it on zeros. The adjacency list stores, for each vertex, only the vertices it is actually connected to.

graph LR
  0 --- 1
  0 --- 2
  1 --- 2
  2 --- 3
TEXT
0: [1, 2]
1: [0, 2]
2: [0, 1, 3]
3: [2]

An undirected edge {u, v} appears twice: v in the list of u and u in the list of v. A directed edge (u, v) appears once, in the list of u.

In Python: dict of lists

The idiomatic Python adjacency list is a dict mapping each vertex to a list (or set) of neighbors. defaultdict(list) removes the need to create empty lists.

Python Adjacency list with defaultdict

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Lists or sets?

Storage Neighbors Edge test u-v Notes
list O(deg) O(deg) Keeps order, allows parallel edges
set O(deg) O(1) average No duplicates, no order

Use a set if you need fast edge tests and the graph is simple. Use a list if you need a stable order or a multigraph.

Weighted and directed versions

For weights, map each neighbor to its weight, or store (neighbor, weight) pairs.

Python Weighted directed adjacency list

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Storing only outgoing arcs makes "who points to me?" slow. If you need it often, keep a second structure for reverse adjacency.

Cost summary

Operation Adjacency list Adjacency matrix
Memory O(n + m) O(nยฒ)
List neighbors of v O(deg v) O(n)
Edge test u-v O(deg u) list, O(1) set O(1)
Visit all edges O(n + m) O(nยฒ)
Add edge O(1) O(1)

Graph traversals such as BFS and DFS visit every neighbor of every vertex, so with lists they run in O(n + m). That is why lists are the default in practice.

Measuring the difference

Python List versus matrix on a sparse graph

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Mutating while iterating

A frequent bug: removing an edge by deleting from a list while you loop over the same list. Loop over a copy, or build a new list. When deleting an undirected edge, remember to remove both directions, otherwise the list becomes inconsistent: u still lists v, but v no longer lists u.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. How many total entries does the adjacency list of an undirected graph with m edges hold?

    Every undirected edge {u, v} is stored twice: v in u's list and u in v's list.
  2. 2. Which representation is usually best for a large sparse graph?

    It uses O(n + m) memory, proportional to the real size of the graph.
  3. 3. In a directed graph stored only as outgoing adjacency lists, which question is slow to answer?

    Finding in-neighbors requires scanning every list unless you also store reverse adjacency.
  4. 4. Which choice gives O(1) average edge tests in a simple graph?

    Hash sets answer membership in constant average time.

Summary

  • An adjacency list maps each vertex to its neighbors; undirected edges appear twice.
  • In Python use dict of list, set or dict (for weights).
  • Memory is O(n + m) and traversals take O(n + m).
  • Sets give fast edge tests; lists preserve order and parallel edges.
  • Directed lists store each arc once; keep reverse lists if you need in-neighbors.

Next: Edge Lists and Incidence Matrices