Graph Search & Pathfinding

Graph search is the most common pattern in AI-enabled interviews — it shows up in friend recommenders, maze solvers, route planners, and grids of all kinds. It's also the pattern where the AI is most likely to hand you a textbook solution that's technically correct but wrong for your constraints.

What it solves

Any problem about navigating networks, finding shortest paths, or exploring connected structures. If you can model the problem as nodes and edges, graph search is on the table: social graphs (who knows whom), grids (mazes, boards), maps (routes, transfers), and dependency structures.

Recognition signals

• "Shortest path", "minimum number of steps", "nearest", "reachable"
• "Friends", "connections", "neighbors", "network", "nodes"
• A grid, board, or matrix where movement between cells matters
• "At most k steps", "with obstacles", "avoid", "all paths"

If the problem mentions edges with weights (distances, costs, times), you're past plain BFS.

The approach

Pick the search from your constraints:

The decision tree: unweighted and shortest → BFS. Just exploring → DFS. Weighted → Dijkstra. Weighted and huge with a natural heuristic → A*.

For grids, remember you're building a graph implicitly: each cell's neighbors are its four (or eight) adjacent cells, and bounds-checking is the graph. A visited set prevents revisits, and BFS guarantees the first time you pop a node it's on the shortest path.

What to tell the AI

Decide the search, then direct the implementation with codebase vocabulary:

Implement BFS on the Grid class: starting at the start coordinate, return the shortest path as a list of coordinates using the existing getNeighbors(cell) method. Track a visited set, and stop at the first visit to the target. Use a Map from cell to parent for path reconstruction.

Solve the maze.

What to verify

The classic AI bugs in this pattern:

• Neighbor expansion — missing diagonals, off-by-one bounds, wrapping around grid edges instead of stopping.
• Visited discipline — marking visited too late (re-enqueuing), or never (infinite loop).
• Path reconstruction — returning distances when asked for the path, or paths in reverse.
• Wrong algorithm — Dijkstra on an unweighted graph when BFS is simpler; DFS "shortest path" that isn't shortest.
• Weights ignored — treating a weighted graph as unweighted.

Worked micro-example

A 3×3 grid, start at (0,0), target at (2,2), no walls. BFS expands: (0,0) → (0,1),(1,0) → ... The shortest path has length 4 (4 moves). The first time BFS dequeues (2,2), it's guaranteed minimal — that's the property that makes BFS correct here, and it's worth narrating.

Practice problems

Try these against this pattern: Friend Recommender (BFS, k-degree), Maze Solver (BFS/DFS with constraints), Route Planner (Dijkstra/A*), and Gridbot (pathfinding plus a command language).