Graphs, Grids & Traversal
Build an adjacency list, treat grids as graphs, and explore with DFS and BFS.
14 min, 0 of 4 activities solved
View cheatsheetGetting Python ready… examples can run in a moment.
A graph is a set of nodes (vertices) joined by edges. Edges can be:
- undirected (friendship: A–B goes both ways) or directed (a follows B, course A needs B)
- unweighted (every step costs the same) or weighted (roads with distances)
Interview problems rarely say "graph". They say islands, friends, prerequisites, flights, a maze, transform one word into another. If the problem is about things and the connections between them, and you need to know what is reachable, connected, or how far, it's a graph problem.
Representations. Input usually arrives as an edge list. Convert it into an adjacency list: a dict from each node to its neighbours.
An undirected graph with two components
Edge list: [(0, 1), (0, 2), (1, 3), (2, 3), (4, 5)]
The same graph as an adjacency list:
0: [1, 2] 1: [0, 3] 2: [0, 3]
3: [1, 2] 4: [5] 5: [4]
The adjacency list lets you ask "who are my
neighbours?" in O(1) and uses O(V + E) memory. (An
adjacency matrix V × V is rarely worth it: O(V²)
memory even for sparse graphs.)
Edge list → adjacency list
defaultdict(list) creates an empty list the first
time you touch a node, so there is no "if node not in
graph" dance. For a directed graph, drop the
second append.
What does this print?
Grids are graphs in disguise. Each cell is a node; its neighbours are the cells up, down, left and right (the "4 directions"). You never build an adjacency list: you compute neighbours on the fly and check the bounds.
Neighbours of a grid cell
The bounds check comes first so grid[nr][nc]
never sees a negative index (which Python would
happily wrap around to the other side!).
Traversal means visiting every node you can reach from a start. Two flavours, one rule: keep a visited set, or cycles will loop forever.
- DFS (depth-first) dives down one path before backtracking. Use recursion or an explicit stack.
- BFS (breadth-first) visits in rings: all nodes
1 step away, then 2 steps, ... Use a queue
(
collections.deque).
Both visit each node and each edge once: O(V + E) time, O(V) extra space. For a grid that's O(rows × cols).
DFS (recursive & iterative) and BFS
DFS runs 0 → 1 → 3 → 5 → 4 → 2, one long path.
BFS goes ring by ring: 0, then 1, 2, then
3, 4, then 5. Swap deque/popleft for a
list and pop() and the same loop explores
depth-first instead (here: 0, 2, 4, 5, 3, 1).
DFS from 0 (recursive)
Mark 0 seen. graph[0] = [1, 2]: 1 is unseen, so recurse into it right away, before even looking at 2.
BFS from 0
Start: seen = {0}, queue = [0].
d = edges from 0, i.e. the ring the node belongs to.
What does this print?
Connected components. One traversal only finds what is reachable from its start. To split the whole graph into groups, loop over every node and launch a traversal from each one that is still unvisited. Each launch discovers exactly one component. This "outer loop + traversal" shape is the whole of Number of Islands.
Label every component
Nodes 5 and 6 have no edges, yet each still forms its
own component: that's why the outer loop runs over
range(n), not over the keys of graph.
Largest group of friends
There are n people labelled 0..n-1 and a list
of friendships edges (undirected pairs). Write
largest_group(n, edges) that returns the size of
the largest connected component.
largest_group(6, [(0, 1), (1, 2), (3, 4)]) is
3 (people 0, 1, 2). With no edges every person is
alone, so the answer is 1 (or 0 when n is
0).
A graph has V nodes and E edges stored as an adjacency list. What does a full BFS cost?