Patterns / Graph Traversal

Graph Traversal Pattern

Model entities as nodes and relationships as edges, then explore with DFS or BFS. Grids are graphs in disguise.

What it is

A graph problem is any problem about things connected to other things. Once you see the nodes and edges, the toolkit is small: DFS or BFS to explore, a visited set to avoid revisiting, and BFS specifically for shortest paths in unweighted graphs. Two-dimensional grids are graphs where each cell connects to its neighbors, so island and maze problems are graph traversals wearing a costume.

When to use it — the signals

• Connected components, "number of islands", or reachability.
• Shortest path / fewest steps in an unweighted graph → BFS.
• Dependencies and ordering → topological sort.
• A grid where you move between adjacent cells.

How it works

A representative implementation in Java:

// Count islands in a grid with DFS flood fill.
void sink(char[][] g, int r, int c) {
    if (r < 0 || c < 0 || r >= g.length || c >= g[0].length || g[r][c] != '1') return;
    g[r][c] = '0';                       // mark visited
    sink(g, r+1, c); sink(g, r-1, c);
    sink(g, r, c+1); sink(g, r, c-1);
}

Complexity

O(V + E) — each node and edge is visited once. For a grid, O(rows × cols).

Common pitfalls

• Forgetting the visited set and looping forever on cycles.
• Using DFS for a shortest-path question (it finds a path, not the shortest).
• Stack overflow from deep recursion on large grids — prefer an explicit stack or BFS.

Practice problems

Classic problems where this pattern is the intended approach: Number of Islands, Course Schedule, Rotting Oranges, Clone Graph. Work through them on the Leet Study home page.