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. If you zoom out, a surprising number of problems reduce to "find a path through a graph." Once you see that, the solution is nearby.
Nobody expects you to walk in with Dijkstra's memorized line by line. Your trusty AI can write any of these algorithms in seconds. What interviewers care about is whether you can spot that a problem is a graph problem in the first place, pick a sensible traversal, explain to them what the algorithm is doing, and steer the AI through the back-and-forth without getting lost. 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 (not only does this apply to most real-world graphs, but it also means that it's tractable to include test cases with largish graphs without requiring huge binaries).
Adjacency List
Python
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. This is better for dense graphs or when you need O(1) edge lookups, but uses memory.
Adjacency Matrix
Python
# 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.
Junior candidates often only spot graphs when they're literally in the prompt: "social network", or "dependency graph". But a lot of the power of a graph representation is that they apply to things more abstract things like game-playing where the edges might represent possible moves. You'll need to be creative in spotting them!
Graph traversal algorithms
Four algorithms cover almost everything you'll see: BFS and DFS for unweighted graphs, Dijkstra's for weighted graphs, and A* when you have a way to estimate distance to the goal. The right pick falls out of the problem shape, so it's worth knowing what each one buys you.
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:
Breadth-First Search
Python
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 None
The 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.
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.
DFS (Recursive)
Python
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 None
You can also write DFS iteratively with an explicit stack, which avoids recursion depth limits for large graphs:
DFS (Iterative)
Python
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 None
DFS 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. As DFS walks down a path, it can mark nodes as "currently on the stack." Bumping into one of those again means you've looped back, which is a cycle.
- Topological sorting (see the topological sort article). Finishing order from DFS naturally produces a valid ordering of nodes that respects dependencies.
- Finding any path (not necessarily shortest). When you just need a solution, going deep is often faster than expanding the whole frontier level by level.
- Exploring all possible paths (e.g., maze solving, backtracking problems). DFS pairs naturally with the choose/explore/unchoose rhythm because the recursion stack already tracks where to back up to.
- Connected component detection. Start DFS from each unvisited node; everything you touch is one component. Repeat until every node has been seen.
- Problems with deep recursive structure. If the problem itself is recursive (trees, nested expressions, fractal-like state), DFS's recursion mirrors the structure for free.
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.
A common mistake candidates make is to request a DFS solution for a shortest path problem. The AI will often happily comply, and you'll notice it's not working when your large test cases timeout.
The reason for this is simple: if there's a 10 hop path from A to B, BFS doesn't have to explore any paths larger than 10! DFS, on the other hand, will happily go cave diving into an abyss of hundreds of hops before it comes back.
Choose carefully!
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.
The reason BFS gives you shortest paths for free is that it processes nodes in order of distance from the start. The first time it reaches any node, that has to be by the fewest edges. DFS makes no such promise; it commits to a direction until it bottoms out, so the path it finds first is usually a long detour.
When in doubt, BFS is the safer default.
Weighted graphs and Dijkstra's algorithm
So far we've assumed every edge has the same weight. 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.
Dijkstra's Algorithm
Python
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"), None
The graph representation changes slightly for weighted graphs — instead of a list of neighbors, each entry is a tuple of (neighbor, weight):
Weighted Graph
Python
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.
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". You'll be looking for the priority queue or heap. Then verify the output has the right structure: a heap, a visited set, and distance tracking.
Your interviewer wants to see some signals that you know what you're looking at, not accepting any implementation as passing.
A*: Dijkstra's with a heuristic
A* is Dijkstra's smarter cousin. The insight for it is pretty 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. As a concrete example: if you're at grid cell (2, 3) and the goal is (5, 7), the Manhattan distance is |5-2| + |7-3| = 7. You don't actually know if there's a clear path that short (there could be walls), but you know any real path has to be at least that long. That's the property A* uses to decide which frontier node to expand next.
The heuristic has to be admissible: it can never overestimate the actual cost. If it does, A* might rule out the optimal path before ever exploring it. Manhattan distance is admissible on a 4-directional grid because the real path can never be shorter than walking straight to the goal.
Problems with heuristics show up a lot in AI coding interviews in part because there's often no "book" answer. A* is a great example of a way to utilize these heuristics, and they'll show up in other approaches like branch and bound which we'll cover in the backtracking pattern.
This basically means A* is most useful in scenarios where there is some structure to the problem that can be used to estimate the cost to the goal like if the problem involves spatial pathfinding (grid navigation, map routing, robot movement). In these cases, 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.
A* Search
Python
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"), None
For a 2D grid where nodes have coordinates:
Heuristic Functions
Python
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.5
If you have a heuristic or an estimate for the cost to the goal, you should probably be thinking about using A*.
What interviewers actually expect
When a graph problem comes up in an AI coding interview, here's what interviewers want to see:
-
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 to the interviewer, not the AI. Once you've identified it as a graph problem, say to your interviewer: "This is an unweighted shortest path problem, so I'm thinking BFS." That takes five seconds and demonstrates real understanding. When you prompt the AI, leave a little room. "Find the shortest path between these nodes" is better than locking it to BFS in the prompt — the AI might suggest something better suited to the specifics, and you want to keep that door open. The interviewer cares that you know what you're picking and why, not that you over-constrained the AI.
-
Be able to explain the algorithm and any variation. When the AI returns code, you should be able to walk through what it does, what data structures it leans on, and where it diverges from the textbook version. "It's BFS, but with a tuple of (node, distance) instead of a separate distance map" is the kind of thing you want to be able to narrate. If you can't competently explain it, the interviewer can't tell whether you understood the choice or got lucky.
-
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.
Finally, we'll want to mention a few edge cases 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)
These edge cases may not actually be part of the provided test cases/data for your problem! But noticing them shows completeness of solution, if you're already thinking about a graph it's way easier to notice that there may be cycles than if you had not identified the graph in the first place.
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
Some interviewers will quiz you about time complexity, but graph time complexities are hairy and "bookish" so they're not tested as agressively as the time complexities of other algorithms.
| 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 since 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.
A great prompt to burn cycles is to write test cases or a harness to validate the heuristic. If you're going to spend time optimizing it, it's nice to have a way to verify that it's working as expected.
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 answer the question from the interviewer before hands-on-keyboard to realize that "minimum number of bus transfers to reach a destination" is 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 of 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