What it is
A graph problem asks you to reason about connections rather than sequences: nodes and the edges between them, which may be directed or undirected, weighted or not. Most of these questions are really "is this the graph in disguise" puzzles — a grid of cells, a list of words, or a set of equations all turn into an implicit graph once you name the nodes and the adjacency rule. Once you see the graph, the algorithm is usually one of a handful of standard traversals: BFS for shortest paths in unweighted graphs, DFS or Kahn's algorithm for ordering and cycle detection, Dijkstra when edges carry non-negative weights.
When it applies
- The input is naturally relational: an adjacency list, a grid, prerequisites, routes, or equations linking entities.
- You need reachability, shortest path, connectivity, ordering, or a yes/no about cycles.
- The state space is small enough to visit each node/edge a bounded number of times; if instead you need to search over subsets or combinations, that is backtracking, not graph traversal.
- Watch two look-alikes: counting connected components with no shortest-path requirement is often cleaner as union-find; and a graph where you must merge or repeatedly test "same group" queries is also better served by union-find than by re-running DFS each time.
Tells in the problem
- "Prerequisite", "must come before", or "recover a valid order" — build a directed graph and topologically sort it.
- A grid where you move up/down/left/right and need to count regions or the shortest number of steps — treat cells as nodes.
- "Minimum number of X to reach Y" where X is not a distance in the usual sense (buses ridden, transformations applied, stops flipped) — the graph's nodes are the thing you're counting, not the surface-level positions.
- Values that must be reconciled through chained ratios or relationships ("if you know A/B and B/C...") — weighted directed edges and a path product.
- "Return -1 if impossible" alongside a request for the minimum something — almost always a BFS/Dijkstra whose sentinel is unreached nodes.
The classic mistake
The most common failure is choosing the wrong unit for "distance". Interviewers report seeing candidates run BFS over the literal input elements (stops, characters, cells) when the quantity being minimized is something else entirely — the number of buses boarded, not stops visited; the bottleneck elevation on a path, not its length. The code still compiles and passes tiny examples because on small graphs the wrong unit and the right one often agree, but it falls apart or times out once routes overlap heavily or the grid gets large. Catch this by writing one sentence before coding: "a node in my graph represents ___, and one step means ___" — if that sentence doesn't match what the problem asks you to minimize, the graph is modeled wrong.
Questions to start with
- Number of Islands — the purest connected-components exercise: flood fill from every unvisited land cell.
- Course Schedule — cycle detection on a directed graph via Kahn's algorithm, the base case for every ordering question.
- Word Ladder — forces you to build the graph implicitly (word adjacency) before BFS finds the shortest path.
- Network Delay Time — the standard Dijkstra template once edges carry weights.
- Bus Routes — the twist: the thing you minimize (buses boarded) is not the surface-level graph (stops), so you must choose the right nodes before searching.