Search
⌘K
Common Patterns
Graph Search & Pathfinding
BFS, DFS, Dijkstra's, and A* — why graph traversal shows up constantly in AI coding problems and how to recognize when you need it.
Graph problems are everywhere in AI coding interviews. Navigation between waypoints, network packet routing, dependency resolution, social network analysis, game state exploration — a surprising number of problems reduce to "find a path through a graph." Once you see that, the solution often writes itself.
The good news: interviewers don't expect you to walk in with Dijkstra's algorithm memorized line by line. What they want is for you to recognize that a problem is a graph problem, pick the right traversal strategy, and direct the AI to implement it correctly. That recognition skill is what separates candidates who flounder for twenty minutes from those who get to a working solution in five.
What is a graph?
A graph is a collection of nodes (sometimes called vertices) connected by edges. That's it. If you can model something as "things" and "connections between things," you've got a graph.
There are two standard ways to represent a graph in code, and you should know both because the AI will ask (or assume) one or the other.
Adjacency list — each node stores a list of its neighbors. This is the default for most interview problems because it's memory-efficient for sparse graphs (which most real-world graphs are).
graph = {
"A": ["B", "D"],
"B": ["A", "C", "D", "E"],
"C": ["B", "E"],
"D": ["A", "B", "E", "F"],
"E": ["B", "C", "D", "F"],
"F": ["D", "E"],
}Adjacency matrix — a 2D grid where matrix[i][j] = 1 means there's an edge from node i to node j. Better for dense graphs or when you need O(1) edge lookups, but uses O(V^2) memory.
# A B C D E F
matrix = [
[0, 1, 0, 1, 0, 0], # A
[1, 0, 1, 1, 1, 0], # B
[0, 1, 0, 0, 1, 0], # C
[1, 1, 0, 0, 1, 1], # D
[0, 1, 1, 1, 0, 1], # E
[0, 0, 0, 1, 1, 0], # F
]In practice, you'll almost always use adjacency lists. If the AI generates a matrix representation and the graph is sparse, that's a red flag worth catching.
When you encounter a new problem in the interview, don't immediately think about algorithms. First ask: "Can I model this as a graph?" If yes, figure out what the nodes are, what the edges are, and whether edges have weights. The algorithm choice follows from that.
BFS: Breadth-First Search
BFS explores a graph level by level. It visits all neighbors of the starting node first, then all neighbors of those neighbors, and so on. Think of it like dropping a stone in a pond — the ripple expands outward uniformly.
This property makes BFS the go-to algorithm for finding the shortest path in an unweighted graph. Because it explores nodes in order of their distance from the start, the first time it reaches any node is guaranteed to be via the shortest path.
Starting from node A, BFS visits nodes in the order shown. Nodes at distance 1 (B, D) come before nodes at distance 2 (C, E), which come before nodes at distance 3 (F). The darker teal nodes have been visited; the lighter node is last in the queue.
Here's a clean BFS implementation:
from collections import deque
def bfs(graph, start, target):
queue = deque([(start, [start])])
visited = {start}
while queue:
node, path = queue.popleft()
if node == target:
return path
for neighbor in graph[node]:
if neighbor not in visited:
visited.add(neighbor)
queue.append((neighbor, path + [neighbor]))
return NoneThe key data structure is the queue (FIFO). Nodes go in at the back and come out at the front, which enforces the level-by-level ordering. The visited set prevents cycles from causing infinite loops.
A common mistake the AI makes with BFS: it'll mark nodes as visited when they're dequeued instead of when they're enqueued. This still works for correctness, but it wastes time by adding duplicate entries to the queue. If you see the visited.add() call inside the while loop instead of inside the for loop, flag it.
When to use BFS:
- Shortest path in an unweighted graph
- Level-order traversal (e.g., "find all nodes within K hops")
- Any problem that asks for the minimum number of steps
DFS: Depth-First Search
DFS takes the opposite approach. Instead of exploring broadly, it goes as deep as possible down one path before backtracking. It's like exploring a maze by always taking the first turn you see and only backing up when you hit a dead end.
def dfs(graph, start, target, visited=None):
if visited is None:
visited = set()
visited.add(start)
if start == target:
return [start]
for neighbor in graph[start]:
if neighbor not in visited:
result = dfs(graph, neighbor, target, visited)
if result:
return [start] + result
return NoneYou can also write DFS iteratively with an explicit stack, which avoids recursion depth limits for large graphs:
def dfs_iterative(graph, start, target):
stack = [(start, [start])]
visited = set()
while stack:
node, path = stack.pop()
if node == target:
return path
if node in visited:
continue
visited.add(node)
for neighbor in graph[node]:
if neighbor not in visited:
stack.append((neighbor, path + [neighbor]))
return NoneDFS doesn't guarantee shortest paths. The path it finds depends entirely on the order it explores neighbors. So why use it?
When to use DFS:
- Cycle detection
- Topological sorting (see the topological sort article)
- Finding any path (not necessarily shortest)
- Exploring all possible paths (e.g., maze solving, backtracking problems)
- Connected component detection
- Problems with deep recursive structure
DFS uses less memory than BFS in practice. BFS has to store the entire frontier (which can be huge for wide graphs), while DFS only stores the current path. For very large graphs, this matters.
Here's a quick heuristic: if the problem asks for "shortest" or "minimum," reach for BFS. If it asks for "all paths," "any path," or involves backtracking, reach for DFS. When in doubt, BFS is the safer default because it gives you shortest paths for free.
Weighted graphs and Dijkstra's algorithm
So far we've assumed every edge has the same cost. Real problems often don't work that way. In a road network, different roads have different distances. In a network, different links have different latencies. When edges have weights, BFS no longer gives you the shortest path — it gives you the path with the fewest edges, not the lowest total weight.
Enter Dijkstra's algorithm. It's essentially BFS, but instead of a regular queue, it uses a priority queue (min-heap) that always processes the node with the smallest known distance first. This guarantees that when you reach a node, you've found the cheapest path to it.
import heapq
def dijkstra(graph, start, target):
heap = [(0, start, [start])]
visited = set()
while heap:
cost, node, path = heapq.heappop(heap)
if node == target:
return cost, path
if node in visited:
continue
visited.add(node)
for neighbor, weight in graph[node]:
if neighbor not in visited:
heapq.heappush(heap, (cost + weight, neighbor, path + [neighbor]))
return float("inf"), NoneThe graph representation changes slightly for weighted graphs — instead of a list of neighbors, each entry is a tuple of (neighbor, weight):
graph = {
"A": [("B", 4), ("D", 2)],
"B": [("A", 4), ("C", 3), ("D", 1)],
"C": [("B", 3), ("E", 6)],
"D": [("A", 2), ("B", 1), ("E", 5), ("F", 3)],
"E": [("C", 6), ("D", 5), ("F", 2)],
"F": [("D", 3), ("E", 2)],
}In this graph, the shortest path from A to C isn't the direct A-B-C route (cost 7). It's A-D-B-C (cost 6), because the detour through D is cheaper. Dijkstra's finds this automatically.
Dijkstra's doesn't work with negative edge weights. If your problem has negative weights, you need Bellman-Ford instead. This is rare in interviews, but if you spot negative weights, mention it to the interviewer — it shows you understand the algorithm's constraints, not just its code.
You don't need to implement Dijkstra's from memory. What matters is recognizing when a problem is a weighted shortest-path problem and knowing to tell the AI "use Dijkstra's with a min-heap." Then verify the output has the right structure: a heap, a visited set, and distance tracking.
A*: Dijkstra's with a heuristic
A* is Dijkstra's smarter cousin. The insight is simple: if you have some idea of which direction the target is in, you can prioritize nodes that seem closer to the goal. Instead of sorting the heap by cost_so_far, A* sorts by cost_so_far + estimated_cost_to_goal.
That estimated cost is the heuristic function, often called h(n). For grid-based pathfinding, Manhattan distance or Euclidean distance are common choices. The heuristic has to be admissible — it should never overestimate the actual cost — otherwise A* might miss the optimal path.
import heapq
def astar(graph, start, target, heuristic):
heap = [(heuristic(start, target), 0, start, [start])]
visited = set()
while heap:
_, cost, node, path = heapq.heappop(heap)
if node == target:
return cost, path
if node in visited:
continue
visited.add(node)
for neighbor, weight in graph[node]:
if neighbor not in visited:
new_cost = cost + weight
priority = new_cost + heuristic(neighbor, target)
heapq.heappush(heap, (priority, new_cost, neighbor, path + [neighbor]))
return float("inf"), NoneFor a 2D grid where nodes have coordinates:
def manhattan_distance(a, b):
return abs(a[0] - b[0]) + abs(a[1] - b[1])
def euclidean_distance(a, b):
return ((a[0] - b[0]) ** 2 + (a[1] - b[1]) ** 2) ** 0.5In practice, here's when A* matters: if the problem involves spatial pathfinding (grid navigation, map routing, robot movement), A* will be significantly faster than plain Dijkstra's because it avoids exploring nodes in the wrong direction. For abstract graphs without spatial structure, A* degrades to Dijkstra's because there's no useful heuristic.
When should you tell the AI to use A* instead of Dijkstra's? If the nodes have coordinates or positions in some space, A* is almost certainly the right call. If the graph is abstract (dependency resolution, state machine transitions), stick with Dijkstra's — there's no meaningful heuristic to exploit.
What interviewers actually expect
When a graph problem comes up in an AI coding interview, here's the playbook that gets high marks.
Recognition is the hard part. Many problems don't say "here's a graph" explicitly. A problem about finding the shortest sequence of word transformations? That's BFS on a graph where each word is a node and edges connect words that differ by one letter. A problem about network connectivity? Graph with connected components. The interviewer is watching whether you can see the graph structure hiding inside the problem description.
Name the algorithm before prompting. Once you've identified it as a graph problem, tell the interviewer (and the AI) which algorithm you're going to use and why. "This is an unweighted shortest path problem, so I'll use BFS" takes five seconds and demonstrates real understanding. Then prompt the AI with that specific direction.
Verify the generated code against known patterns. When the AI gives you a BFS implementation, quickly check: Does it use a queue? Does it track visited nodes? Does it mark visited on enqueue, not dequeue? For Dijkstra's: Is there a min-heap? Does it skip already-visited nodes? These are fast sanity checks that catch the most common AI mistakes.
Watch for the grid-as-graph pattern. A huge number of interview problems involve 2D grids. The AI might try to write a specialized grid traversal, but you can often simplify by pointing out that a grid is just a graph where each cell connects to its 4 (or 8) neighbors. This reframes the problem into a standard graph algorithm.
Edge cases to mention proactively:
- Disconnected graphs (target might be unreachable)
- Self-loops and duplicate edges
- Very large graphs (does the solution scale?)
- The graph being a tree (simplifies many algorithms since there are no cycles)
If you're uncertain which algorithm fits, say so. "I think this is a shortest-path problem with weighted edges, so Dijkstra's should work. Let me verify that the weights are all non-negative." This kind of transparent reasoning scores better than silently picking an algorithm and hoping it's right.
Tradeoffs at a glance
| Algorithm | Time Complexity | Space Complexity | Best For |
|---|---|---|---|
| BFS | O(V + E) | O(V) | Shortest path in unweighted graphs, level-order traversal |
| DFS | O(V + E) | O(V) | Cycle detection, topological sort, exhaustive search, connected components |
| Dijkstra's | O((V + E) log V) | O(V) | Shortest path in weighted graphs with non-negative weights |
| A* | O((V + E) log V) | O(V) | Spatial pathfinding where a good heuristic exists |
A few things worth noting about this table. BFS and DFS have the same theoretical complexity, but their memory profiles differ in practice — BFS stores the entire frontier while DFS only stores the current path. Dijkstra's and A* also have the same worst-case complexity, but A* is faster in practice when the heuristic is good because it explores fewer nodes.
The log V factor in Dijkstra's and A* comes from the heap operations. If you're using Python's heapq, this is handled for you. If the AI generates a solution that uses a sorted list instead of a heap, flag it — that turns the complexity into O(V^2), which matters for large graphs.
Don't memorize this table. Instead, internalize the decision tree: Is the graph weighted? If no, use BFS for shortest path or DFS for exploration. If yes, are there coordinates or spatial positions? If yes, use A*. If no, use Dijkstra's. That's the whole decision process, and it covers the vast majority of interview problems.
Putting it together
Graph search is one of those patterns where recognition matters far more than implementation. In an AI coding interview, the AI can generate BFS, DFS, or Dijkstra's in seconds. What it can't do is look at a problem about "minimum number of bus transfers to reach a destination" and realize that's a BFS problem on a graph where bus routes are nodes.
That insight is yours to bring. Practice spotting graph structure in problems that don't obviously look like graph problems. When you see one, name the algorithm, explain your reasoning to the interviewer, and let the AI handle the boilerplate. Then verify the output against the patterns you know: queues for BFS, stacks for DFS, heaps for Dijkstra's and A*. That workflow — recognize, direct, verify — is exactly what interviewers are looking for.
Purchase Premium to Keep Reading
Unlock this article and so much more with Hello Interview Premium
Reading Progress
On This Page
Schedule a mock interview
Meet with a FAANG senior+ engineer or manager and learn exactly what it takes to get the job.
