Graph problems separate candidates who memorize solutions from those who recognize patterns. At Google, Meta, Amazon, and most well-funded startups, at least one graph question shows up in nearly every onsite loop — and roughly 80% of them reduce to two techniques: breadth-first search (BFS) and depth-first search (DFS). Master these two traversal patterns and you unlock islands, mazes, course schedules, social networks, and dozens of other problem families in one move.
Why Graph Problems Matter in 2026 Interviews
Interviewers love graphs because they test modeling, not just coding. Many graph questions never say the word “graph” — they talk about flight routes, prerequisite courses, infected servers, or word ladders. The real skill being evaluated is whether you can look at a messy real-world description and say: these are nodes, these are edges, and this is a traversal problem. That modeling step is exactly what day-to-day engineering requires, which is why graph questions have remained a staple even as interview formats evolve.
Graph Representations: Start With the Adjacency List
Before any traversal, you need a representation. In interviews, the adjacency list wins almost every time — it is memory-efficient for sparse graphs and trivial to build from an edge list:
Map<Integer, List<Integer>> graph = new HashMap<>();
for (int[] edge : edges) {
graph.computeIfAbsent(edge[0], k -> new ArrayList<>()).add(edge[1]);
graph.computeIfAbsent(edge[1], k -> new ArrayList<>()).add(edge[0]); // undirected
}For grid problems (islands, mazes, rotting oranges), the 2D matrix itself is the graph: each cell is a node, and the four directional moves are its edges. You rarely need to build an explicit structure — a directions array {{1,0},{-1,0},{0,1},{0,-1}} does the job.
The BFS Pattern
When to Use BFS
Reach for BFS whenever the question mentions shortest path, minimum steps, nearest, or level-by-level processing on an unweighted graph. Because BFS explores all nodes at distance k before any node at distance k+1, the first time you reach a target is guaranteed to be via a shortest path.
The BFS Template
int bfs(Map<Integer, List<Integer>> graph, int start, int target) {
Queue<Integer> queue = new ArrayDeque<>();
Set<Integer> visited = new HashSet<>();
queue.offer(start);
visited.add(start);
int steps = 0;
while (!queue.isEmpty()) {
int size = queue.size(); // process one level at a time
for (int i = 0; i < size; i++) {
int node = queue.poll();
if (node == target) return steps;
for (int next : graph.getOrDefault(node, List.of())) {
if (visited.add(next)) queue.offer(next);
}
}
steps++;
}
return -1;
}Two details matter enormously in interviews. First, mark nodes visited when you enqueue them, not when you dequeue — otherwise the same node enters the queue multiple times and blows up your complexity. Second, the size snapshot is what gives you level-by-level processing, which is essential for “minimum number of steps” answers.
Classic BFS Problems
Practice these in order: Rotting Oranges (multi-source BFS), Word Ladder (implicit graph), Shortest Path in Binary Matrix, and Open the Lock (state-space search). Multi-source BFS — seeding the queue with several starting nodes — is a favorite twist in 2026 loops.
The DFS Pattern
When to Use DFS
DFS is the tool for exhaustive exploration: counting connected components, detecting cycles, topological ordering, and any question asking whether a path exists rather than how short it is. It also underpins backtracking, so a solid DFS foundation pays double.
The DFS Template
void dfs(int node, Map<Integer, List<Integer>> graph, Set<Integer> visited) {
visited.add(node);
for (int next : graph.getOrDefault(node, List.of())) {
if (!visited.contains(next)) {
dfs(next, graph, visited);
}
}
}Counting connected components is then a three-line loop: for every unvisited node, run DFS and increment a counter. That single idea solves Number of Islands, Number of Provinces, and most “group the related items” questions.
Cycle Detection and Topological Sort
For directed graphs, upgrade the visited set to three states: unvisited, in-progress, and done. Seeing an in-progress node again means a cycle. This pattern solves Course Schedule I and II — two of the most frequently reported questions at Amazon and Meta this year. If the interviewer asks for a valid ordering, record nodes in post-order and reverse the result: that is topological sort with almost no extra code.
BFS vs DFS: How to Choose in 30 Seconds
| Signal in the problem | Choose | Why |
|---|---|---|
| Shortest path, fewest moves, nearest | BFS | Level order guarantees minimal distance |
| Count components, flood fill | Either (DFS is shorter) | Full exploration, order irrelevant |
| Cycle detection, ordering with prerequisites | DFS | Three-state coloring and post-order |
| Very deep graphs, recursion limits | BFS or iterative DFS | Avoids stack overflow |
| All paths, combinations of choices | DFS + backtracking | Natural undo-and-retry structure |
A 7-Day Graph Practice Plan
Days 1–2: Grid DFS — Number of Islands, Max Area of Island, Flood Fill. Days 3–4: BFS — Rotting Oranges, Shortest Path in Binary Matrix, Word Ladder. Day 5: Cycle detection and topological sort — Course Schedule I and II. Day 6: Implicit graphs — Open the Lock, Minimum Genetic Mutation. Day 7: Mixed review under a 25-minute timer per problem, coding each template from memory.
Common Mistakes That Sink Candidates
The failures interviewers report are remarkably consistent. Candidates forget the visited set and loop forever. They mark nodes visited at dequeue time and silently degrade BFS to exponential behavior. They use recursion on a graph with a million nodes and hit stack overflow without mentioning the iterative alternative. And they jump into code before stating the node/edge model out loud — losing the easiest communication points of the interview. State your complexity too: both traversals run in O(V + E) time, and saying so unprompted signals seniority.
Final Thoughts
BFS and DFS are not two among fifty patterns — they are the backbone of nearly every graph question you will face in 2026. Learn the two templates until you can write them from memory, practice the decision table until the choice is instant, and spend your remaining prep time on the twists: multi-source BFS, three-state cycle detection, and implicit graphs. Set aside one focused week, follow the plan above, and graph rounds will turn from your weakest area into a reliable win. Tools like Niraswa AI can support your practice — but the templates in this guide are the foundation. Start today: open your editor and write the BFS template from scratch, right now.
