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.

  0 --- 1          edge list:
  |     |          [(0,1), (0,2), (1,3), (2,3)]
  2 --- 3
                   adjacency list:
  4 --- 5          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 BFS turns into a DFS.

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?