Know this before you start: “Adjacency lists and grids as graphs”
Representing graphs: adjacency lists and grids
A graph is nodes and edges. Store each node's neighbours in a list (an adjacency list); a grid is a graph where each cell's neighbours are up, down, left, right.
The idea
Many problems are graphs in disguise: cities and roads, courses and prerequisites, words one letter apart, cells in a grid.
The usual way to store one is an adjacency list: a map from each node to the list of its neighbours, built from the edge list. Directed edges go one way; undirected ones are added both ways.
Grids don't need building: a cell (r, c) has neighbours (r ± 1, c) and (r, c ± 1), as long as they're inside the grid.
See it step by step
Edges [[0, 1], [0, 2], [2, 3]], undirected
- 0: [1, 2]
- 1: [0]
- 2: [0, 3]
- 3: [2]: now “who is next to 2?” is one lookup.
In code (Python)
from collections import defaultdict
def adjacency(edges, directed=False):
graph = defaultdict(list)
for a, b in edges:
graph[a].append(b)
if not directed:
graph[b].append(a)
return graph
def grid_neighbours(grid, r, c):
for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
nr, nc = r + dr, c + dc
if 0 <= nr < len(grid) and 0 <= nc < len(grid[0]):
yield nr, nc
g = adjacency([[0, 1], [0, 2], [2, 3]])
print(dict(g)) # {0: [1, 2], 1: [0], 2: [0, 3], 3: [2]}
print(list(grid_neighbours([[1, 1], [1, 1]], 0, 0))) # [(1, 0), (0, 1)]Building: O(V + E) time and space.
When you'll use it
- Every graph problem starts by choosing this representation.
Common mistakes
- Adding undirected edges only one way.
- Forgetting nodes with no edges (they still exist).
