Graph Traversal

Tactic

Graph traversal explores nodes and edges while preventing repeated work. DFS and BFS are the two main traversal modes, but the shared idea is visited state.

The invariant is that every processed node has been reached by a valid path from some start. The visited set divides the graph into known and unknown regions.

Representation is part of the tactic. Build an adjacency list for arbitrary node labels, use directional offsets for grids, and decide whether edges are directed before traversal begins.

Value

The value is turning relationships into a systematic walk. Traversal avoids restarting from scratch for every query and prevents cycles from creating infinite loops.

Direct complexity example

Brute force: For each node, scan the whole edge list to find neighbors: $O(VE)$ time in dense implementations.
With this tactic: Build adjacency once and traverse: $O(V + E)$ time.
Space: Space is $O(V + E)$ for adjacency plus $O(V)$ for visited and stack or queue.

Challenges this solves

reachability
connected components
clone graph
course prerequisites
grid islands
bipartite checks

When to use it

Use this tactic when these conditions are true:

entities are connected by relationships
the input has edges, adjacency, or neighbor moves
cycles or disconnected components are possible
the answer depends on what can be reached

When not to use it

Reach for a different tactic when these warning signs appear:

the graph is weighted and asks for minimum cost
the problem is just dependency ordering and topological sort gives the final form
the data is a tree with no cycles and simpler tree traversal works
the graph changes online and needs dynamic connectivity

Terminology clues

These prompt words often point toward this concept:

graph
edge
node
neighbor
connected
component
reachable
visited