LESSON 20 · PATTERN GUIDE

Graph BFS / DFS

Traverse connected vertices while recording which nodes have already been visited.

FIRST, LEARN THE PATTERNDFS follows a path deeply; BFS explores by distance in number of edges. Both use a visited set to avoid repeated work and cycles.

The input describes a grid, network, islands, connected components, or reachability.

How to approach it

Choose adjacency lists for sparse graphs or a grid-neighbor function for matrices; mark nodes visited when adding them to the worklist.

Watch out for

For directed graphs, reachability depends on edge direction. In grids, check bounds and mark visited consistently.

A CLOSER EXPLANATION

Represent each relationship as an edge and traverse from a starting vertex while marking each node visited. DFS is convenient for components and exhaustive reachability; BFS gives minimum edge-count distance when all edges have equal cost. The same idea applies to grid cells by treating neighboring cells as vertices.

NOW YOU TRY

Practice question

How many connected land groups are in this grid, where 1 is land and only horizontal/vertical neighbors connect?

EXAMPLEgrid = [[1,0,1],[1,0,0],[0,0,1]]Give your answer before revealing the explanation.

Show a hint

Start a traversal from every unvisited land cell and count how many traversals begin.

Show an answer

3 groups.

CONNECT IT TO REAL LIFE

Graph BFS / DFS at work

A company network has computers connected by cables. Starting at the server, how can you find all computers that are reachable during a network check?

Show one possible approach

Run DFS or BFS from the server and mark each computer when it is first discovered. The visited set prevents cycles from causing repeated work.

Practice next

Use these problem IDs to find additional practice for this pattern:

20069573399410911254