Number of Islands is a grid puzzle. Course Schedule is about class prerequisites. Word Ladder is about changing one letter at a time. Not one of them says “graph” — and every one of them is graph traversal. Spotting that costume is what this category drills: a grid, a prerequisite list, a ladder of words, each is really a set of nodes and edges.
Once you see the nodes and edges, there are only a couple of things you ever do to them. This hub is about spotting the graph, then picking which of those two things the problem wants.
A tree traversal that’s allowed to loop
A graph is a tree without the guarantee that there’s only one route to each node. Because a node can now be reached from several directions, a graph walk needs one thing a tree walk never did — a record of where it has already been:
void dfs(int node, List<List<Integer>> adj, boolean[] visited) {
if (visited[node]) return; // the whole difference from a tree: don't re-enter
visited[node] = true;
for (int next : adj.get(node)) {
dfs(next, adj, visited);
}
}A rooted-tree recursion over child pointers never needed a visited check because there’s only one path down to any node (an undirected tree stored as an adjacency list still needs to remember its parent). A graph can arrive at the same node from several edges, so without that guard you loop or redo work endlessly. A reachability traversal — recursive DFS, an explicit stack, or a BFS queue — is the tree walk plus “have I been here already?” (Some graph algorithms skip the visited set: Kahn’s works from indegrees, and path enumeration revisits nodes on purpose.)
Two engines, and the question each answers
You reach for one of two traversals, and which one is decided by the question, not by taste:
- BFS (a queue, expanding outward in rings) answers shortest path in an unweighted graph. Because it visits everything one step away before anything two steps away, the first time it reaches a node it has reached it by the fewest edges. Word Ladder and Rotting Oranges are BFS because they ask “how many steps.”
- DFS (recursion or a stack, plunging down one path) answers reachability and structure — is this connected, which nodes belong to one blob. Island-counting and connected-components lean on DFS (or union-find) because they ask “what’s reachable from what.”
If a problem says “shortest” or “fewest,” start a queue. If it says “how many groups” or “can you reach,” start a recursion. Ordering things under dependencies — and the “is there a cycle” that comes with it — is its own case: a topological sort, which Kahn’s algorithm does BFS-style, though a DFS post-order works too (below).
Spotting the disguise
Naming which costume a problem is wearing tells you the representation and the engine in one move:
- A grid is a graph. In island and flood-fill problems every cell is a node and its up/down/left/right neighbors are its edges — no adjacency list required, you compute neighbors from coordinates. Number of Islands, Max Area of Island, Surrounded Regions, Pacific Atlantic Water Flow, Walls and Gates, and Rotting Oranges are all “the grid is the graph,” differing only in where the traversal starts.
- Prerequisites are a directed graph. Course Schedule is “can I order these so every dependency comes first?” — which is exactly topological sort, and its answer is no precisely when there’s a cycle. Kahn’s algorithm makes this concrete: repeatedly take a node with no remaining prerequisites (indegree zero), remove it, and if you can’t drain the whole graph that way, a cycle is stuck inside it.
- Connectivity is union-find’s home turf. Number of Connected Components, Graph Valid Tree, and Redundant Connection all ask whether things are already joined. Union-find answers that in near-constant time per query, and “the edge that connects two already-connected nodes” is precisely the redundant one, or the cycle that stops a graph from being a tree.
The thirteen, by costume
- Grid flood-fill (DFS or BFS): Number of Islands, Max Area of Island, Surrounded Regions, Pacific Atlantic — start from the right cells and mark what you reach.
- Multi-source BFS: Rotting Oranges and Walls and Gates seed the queue with every source at once (all rotten oranges, all gates) so the rings expand in lockstep and distances come out right.
- Shortest transformation (BFS): Word Ladder, where neighbors are words one letter apart.
- Topological sort (cycle-aware): Course Schedule and Course Schedule II — the second just records the drain order.
- Union-find: Number of Connected Components, Graph Valid Tree, Redundant Connection.
- DFS with a hash map: Clone Graph, copying nodes as you first see them and wiring edges on the way.
Where the cycles actually bite
The cycle check you write for Course Schedule is the same one a build system runs on your code. It topologically sorts your modules so each compiles after its dependencies, and a circular dependency is precisely a cycle in that graph. Bazel refuses to order one rather than looping forever, and Gradle fails the build the moment two projects depend on each other in a circle. Deadlock detection is a close relative on a “who is waiting on whom” graph — with single-instance resources a cycle means nobody can proceed, though with multiple instances a cycle is necessary but not always sufficient. Course Schedule isn’t a toy version of that check; it’s the same algorithm on a smaller graph.
Learn to see the graph
Get in the habit of asking two questions of any problem that smells combinatorial: what are the nodes, and what are the edges? Answer them and the thirteen problems collapse into a short list of questions — the shortest path (reach for a BFS queue), the shape of what’s connected (DFS or union-find), or a valid ordering of dependencies (a topological sort). The costumes are endless; the graph under them rarely changes.
References
- NeetCode 150 — Graphs — the thirteen problems mapped here.
