Graph problems show up in roughly three out of every ten coding interview rounds at top tech companies, and for good reason: real systems like maps, social networks, and dependency managers are graphs under the hood. Yet many candidates who have mastered arrays, strings, and trees still freeze the moment a problem says “cities connected by roads” or “employees who report to each other.” The fix isn’t memorizing more problems — it’s internalizing two traversal patterns, breadth-first search (BFS) and depth-first search (DFS), deeply enough that you can recognize which one a problem is really asking for within the first thirty seconds.
This guide breaks down when to reach for each traversal, the five core patterns that generate most graph interview questions, the problems worth practicing first, and how to talk through your approach so interviewers see your reasoning, not just your syntax.
BFS vs. DFS: How to Choose in Seconds
Both algorithms visit every reachable node from a starting point, but they explore in a different order, and that order determines which problems they solve efficiently.
Reach for BFS when the problem involves distance
BFS explores level by level, using a queue. Because it visits all nodes at distance 1 before any node at distance 2, the first time BFS reaches a node is guaranteed to be via the shortest path in an unweighted graph. Any time a problem mentions “minimum steps,” “shortest path,” “fewest moves,” or “levels,” BFS is almost always the right tool. Classic examples include Rotting Oranges, Word Ladder, and Shortest Path in Binary Matrix.
Reach for DFS when the problem involves exploration or structure
DFS explores as far as possible down one path before backtracking, using a stack (explicit or via recursion). It’s the natural choice when you need to explore every possible path, detect cycles, perform a topological sort, or find connected components — problems where you care about the shape of the graph more than the distance between two points. Number of Islands, Course Schedule, and Clone Graph are DFS-friendly staples.
In an interview, say this out loud: “I’m using BFS because I need the shortest path in terms of edges, and BFS guarantees the first time I reach a node it’s via the shortest path.” One sentence like that signals you understand the why, not just the how — and that distinction is often what separates a pass from a borderline decision.
The Five Patterns Behind Most Graph Questions
Interviewers rarely test raw BFS or DFS in isolation. Instead, they layer the traversal underneath one of a handful of recurring patterns. Master these five and you’ll recognize the shape of most graph problems you encounter.
1. Connected Components
Count or label groups of nodes that are reachable from one another. Run DFS or BFS from every unvisited node, incrementing a counter each time you start a new traversal. Number of Islands and Number of Provinces are direct applications.
2. Shortest Path (Unweighted)
Standard BFS from a single source, tracking distance or step count as you expand the queue. Rotting Oranges and 01 Matrix extend this into multi-source BFS, where you seed the queue with several starting points at once instead of one.
3. Cycle Detection
In a directed graph, track nodes currently “in progress” during a DFS traversal (often with a recursion-stack set); revisiting one of those nodes means you’ve found a cycle. In an undirected graph, a cycle exists if you reach an already-visited neighbor that isn’t the node you just came from.
4. Topological Sort
Order nodes so that every directed edge points from an earlier node to a later one — only possible in a directed acyclic graph (DAG). This underlies scheduling problems like Course Schedule and Course Schedule II, and can be implemented with DFS-based postorder reversal or Kahn’s algorithm (BFS with in-degree tracking).
5. Multi-Source and Weighted Shortest Path
When edges have different costs, plain BFS breaks down because it assumes every edge has equal weight. That’s where Dijkstra’s algorithm comes in, using a min-heap to always expand the currently cheapest node first. It’s less frequently required than the first four patterns, but senior-level interviews increasingly expect candidates to at least recognize when Dijkstra applies versus when BFS is sufficient.
Translating the Problem Into a Graph
The hardest part of graph interviews usually isn’t the algorithm — it’s recognizing that a problem is a graph problem at all. Grids, dependency lists, word chains, and even employee hierarchies are all graphs in disguise. Before writing code, ask yourself three questions:
What are the nodes? In a grid problem, each cell is a node. In a scheduling problem, each course or task is a node. What are the edges? Adjacency in a grid, prerequisites in a course list, or one-letter transformations in a word ladder. Is the graph directed or undirected, weighted or unweighted? This single decision determines whether BFS alone is sufficient or whether you need Dijkstra, and whether cycle detection needs a recursion-stack check or a simple visited set.
Interviewers are evaluating your ability to model a real-world situation as a graph and choose an appropriate strategy to explore it — the code is almost secondary to that framing. Spend the first two minutes on the whiteboard sketching a small example, labeling nodes and edges, before you touch the keyboard.
A Two-Week Practice Roadmap
If graphs are your weak spot, don’t jump straight into hard problems. Build the traversal muscle first, then layer on patterns.
Days 1–3: Implement plain BFS and DFS on an adjacency list, both iteratively and recursively, until you can write either from memory in under three minutes. Solve Flood Fill and Number of Islands.
Days 4–7: Move to multi-source and shortest-path variants: Rotting Oranges, 01 Matrix, Word Ladder. Focus on correctly seeding the BFS queue and tracking distance.
Days 8–11: Tackle directed graphs: Course Schedule, Course Schedule II, and Clone Graph. Practice explaining cycle detection out loud before coding it.
Days 12–14: Mix in a weighted problem like Network Delay Time to get comfortable with Dijkstra’s structure, then do two full mock interviews combining a grid problem and a dependency-list problem under time pressure.
Common Mistakes That Cost Candidates the Round
A few errors show up again and again in graph interviews. Forgetting to mark a node as visited before it’s fully processed can cause infinite loops or duplicate work, especially in DFS recursion. Confusing “visited” with “in the current recursion stack” breaks cycle detection in directed graphs. Assuming BFS works for weighted edges leads to wrong shortest-path answers the moment edge costs differ. And treating a grid as though diagonal moves are always included — or always excluded — without confirming with the interviewer wastes time on a wrong first attempt. Clarify these assumptions before you start coding, not after your solution fails a test case.
Start Preparing With a Plan, Not Just a Problem List
Grinding random graph problems without a structure is the slowest way to get comfortable with BFS and DFS. Recognize the pattern first, choose the traversal deliberately, and practice explaining your reasoning as clearly as your code. That combination — pattern recognition plus clear communication — is what consistently moves candidates from “solved it” to “strong hire” in the interviewer’s notes.
If you want structured practice that adapts to where you’re weakest, Niraswa AI is a good place to start building your interview readiness.
