Graphs, Grids & Traversal

Graphs, lesson 1 of 3

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 cheatsheet

Getting 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.

Diagram

An undirected graph with two components

012345

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.)

Example

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.

Quiz

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.

Example

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).

Example

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).

Walkthrough

DFS from 0 (recursive)

012345
Step 1 of 7
calls = dfs(0)
order = [0]

Mark 0 seen. graph[0] = [1, 2]: 1 is unseen, so recurse into it right away, before even looking at 2.

current call
waiting on the call stack
finished
Walkthrough

BFS from 0

0d=012345
Step 1 of 7
queue = [0]
order = []

Start: seen = {0}, queue = [0].

popped now
in the queue
done

d = edges from 0, i.e. the ring the node belongs to.

Quiz

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.

Example

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.

Exercise

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).

Quiz

A graph has V nodes and E edges stored as an adjacency list. What does a full BFS cost?