Graph problems are among the most frequently tested topics in technical interviews at top companies like Google, Meta, Amazon, and Microsoft. Yet many candidates spend disproportionate time on arrays and strings while neglecting this critical area. If you want to stand out in 2026 coding interviews, mastering Breadth-First Search (BFS) and Depth-First Search (DFS) patterns is non-negotiable.
In this guide, we will break down the core graph traversal patterns, provide reusable templates, and walk through the most common interview problems you are likely to encounter.
Why Graphs Matter in Coding Interviews
Graphs model relationships, and real-world engineering is full of them: social networks, dependency resolution, network routing, recommendation engines, and task scheduling. Interviewers love graph problems because they test multiple skills simultaneously: data structure knowledge, recursion, queue and stack usage, and the ability to think about state and visited tracking.
According to recent data from interviewing platforms, graph problems appear in roughly 25 to 30 percent of coding rounds at FAANG-level companies. That percentage has increased in 2026 as companies look for problems that are harder to solve with AI assistance alone.
BFS: The Level-Order Powerhouse
Breadth-First Search explores nodes level by level using a queue. It is the go-to approach whenever you need the shortest path in an unweighted graph or need to process nodes in order of their distance from a source.
BFS Template
from collections import deque
def bfs(graph, start):
visited = set([start])
queue = deque([start])
while queue:
node = queue.popleft()
# Process the current node
for neighbor in graph[node]:
if neighbor not in visited:
visited.add(neighbor)
queue.append(neighbor)
When to Reach for BFS
Use BFS when the problem asks for the shortest path or minimum number of steps in an unweighted graph, level-order traversal of a tree, finding all nodes within a certain distance, or any scenario where you need to explore closer nodes before farther ones.
Classic BFS Interview Problems
Rotting Oranges (LeetCode 994): This is a multi-source BFS problem. You start by adding all rotten oranges to the queue simultaneously and expand outward level by level. Each level represents one minute of time. The key insight is that multi-source BFS is identical to single-source BFS — you simply initialize the queue with multiple starting nodes.
Word Ladder (LeetCode 127): Transform one word into another by changing one letter at a time, where each intermediate word must be in the dictionary. Model each word as a node and connect words that differ by exactly one character. BFS gives you the shortest transformation sequence.
01 Matrix (LeetCode 542): Find the distance of each cell to the nearest zero. Start BFS from all zero cells simultaneously. This multi-source BFS radiates outward, and the first time you reach a non-zero cell determines its minimum distance.
DFS: The Deep Explorer
Depth-First Search dives as deep as possible along each branch before backtracking. It naturally maps to recursion and is ideal for problems involving path exploration, connectivity, and cycle detection.
DFS Template (Recursive)
def dfs(graph, node, visited):
visited.add(node)
# Process the current node
for neighbor in graph[node]:
if neighbor not in visited:
dfs(graph, neighbor, visited)
DFS Template (Iterative with Stack)
def dfs_iterative(graph, start):
visited = set()
stack = [start]
while stack:
node = stack.pop()
if node in visited:
continue
visited.add(node)
# Process the current node
for neighbor in graph[node]:
if neighbor not in visited:
stack.append(neighbor)
When to Reach for DFS
DFS shines when you need to explore all possible paths, detect cycles, perform topological sorting, find connected components, or solve problems that require backtracking through the graph.
Classic DFS Interview Problems
Number of Islands (LeetCode 200): Given a 2D grid of ones and zeros, count the number of islands. For each unvisited one, launch a DFS that marks all connected ones as visited. Each DFS call discovers one complete island.
Clone Graph (LeetCode 133): Deep copy a graph. Use DFS with a hash map that maps original nodes to their clones. When you visit a node, create its clone, then recursively clone all neighbors.
Course Schedule (LeetCode 207): Determine if you can finish all courses given prerequisite relationships. This is a cycle detection problem on a directed graph. Use DFS with three states: unvisited, in-progress, and completed. If you encounter an in-progress node during traversal, a cycle exists and the schedule is impossible.
Advanced Graph Patterns
Beyond basic BFS and DFS, several advanced patterns build on these fundamentals and appear regularly in interviews.
Topological Sort: Used for ordering tasks with dependencies. Apply DFS and add nodes to the result in reverse post-order, or use Kahn’s algorithm with BFS by processing nodes with zero in-degree first. Common in problems like Course Schedule II and Alien Dictionary.
Union-Find (Disjoint Set Union): Efficiently tracks connected components and supports merge operations. Essential for problems like Number of Connected Components, Redundant Connection, and Accounts Merge. While not strictly BFS or DFS, it solves many of the same connectivity problems more efficiently.
Bipartite Check: Determine if a graph can be two-colored using BFS or DFS. Assign alternating colors to neighbors. If a conflict arises, the graph is not bipartite. Appears in problems like Is Graph Bipartite and Possible Bipartition.
Shortest Path Variants: For weighted graphs, Dijkstra’s algorithm extends BFS using a priority queue. For graphs with negative weights, Bellman-Ford is necessary. Know when each applies — interviewers often test whether you recognize which algorithm fits the constraints.
Graph Problem-Solving Framework
When you encounter a graph problem in an interview, follow this mental checklist. First, identify the graph: what are the nodes and edges? Sometimes the graph is explicit, but often you need to model the problem as a graph. Second, determine if the graph is directed or undirected, weighted or unweighted. Third, identify the pattern: are you looking for shortest path, connectivity, ordering, or cycle detection? Fourth, choose your tool: BFS for shortest paths and level-order processing, DFS for exhaustive exploration and backtracking, topological sort for ordering, and Union-Find for dynamic connectivity.
Common Mistakes to Avoid
Forgetting to track visited nodes is the most common mistake, leading to infinite loops in cyclic graphs. Another frequent error is using DFS when BFS is required — DFS does not guarantee shortest path in unweighted graphs. Also watch out for not handling disconnected components: always iterate over all nodes and launch traversal from any unvisited node, not just from a single starting point.
Practice Roadmap for 2026
Start with the fundamentals: Number of Islands, Flood Fill, and Max Area of Island to build comfort with grid-based DFS. Move to BFS shortest-path problems like Rotting Oranges and Word Ladder. Then tackle topological sort with Course Schedule and Alien Dictionary. Finish with advanced problems like Word Search II, Network Delay Time, and Cheapest Flights Within K Stops.
Aim to solve three to four graph problems per week over four weeks. By the end, these patterns will feel like second nature, and you will approach graph interview questions with the confidence of someone who has a proven framework rather than relying on memorization.
Graph traversal is a skill that compounds. Every new problem you solve reinforces the patterns, and soon you will start recognizing graph structure in problems that do not even mention the word graph. That is when you know you are truly ready.
