Coding interview prep

April 6, 2026

Graph Algorithms for Coding Interviews: When to Use BFS, DFS, or Dijkstra

Graphs are the most feared topic in coding interviews — not because they're impossible, but because most people learn the algorithms in isolation without understanding when to use each one. This guide gives you the decision framework that turns graph problems from guesswork into a systematic process.

In surveys and interview feedback, graphs consistently appear in the top two or three most difficult topics. The reason is specific: candidates know how BFS works and how Dijkstra works, but they freeze when a new problem appears because they don't know which algorithm to reach for.

The decision framework is learnable, and once you have it, graph problems become one of the most predictable categories in an interview. Here's how to build it.

The three graph algorithms every interviewer expects you to know

Before the decision framework, the fundamentals. These three algorithms cover the vast majority of graph interview problems. Know them cold — not as recipes to memorize, but as tools with specific purposes.

BFS — Breadth-First Search

Shortest path in unweighted graphs, minimum steps, level-by-level exploration

Data structure

Queue (FIFO)

Complexity

O(V + E) time, O(V) space

Use when:

You need the shortest path in terms of number of edges (unweighted graph)
You need to find the minimum number of steps to reach a target
You need to explore all nodes at distance k before nodes at distance k+1
You need to find if a path exists and want the shortest one

Don't use when:

The graph has weighted edges — BFS treats all edges as equal cost. Use Dijkstra instead.

Classic interview problems:

Binary Tree Level Order Traversal (LC 102)
Rotting Oranges (LC 994)
Word Ladder (LC 127)
Shortest Path in Binary Matrix (LC 1091)
Number of Islands (LC 200) — also solvable with DFS

Interview tip: Always state explicitly: 'I'm using BFS because I need the shortest path in terms of edges, and BFS guarantees that the first time I reach a node, it's via the shortest path.' That sentence shows the interviewer you understand the why, not just the how.

DFS — Depth-First Search

Exhaustive exploration, path existence, connected components, backtracking

Data structure

Stack (implicit via recursion, or explicit)

Complexity

O(V + E) time, O(V) space

Use when:

You need to detect cycles in a graph
You need to find all paths between two nodes (not just the shortest)
You need to check connectivity or count connected components
You need to solve a problem where you explore fully before backtracking (permutations, combinations)
You need topological sort (DFS-based approach)

Don't use when:

You need the shortest path — DFS doesn't guarantee shortest path. It may find a path, but not necessarily the optimal one.

Classic interview problems:

Number of Islands (LC 200)
Course Schedule (LC 207) — cycle detection in directed graph
Clone Graph (LC 133)
Pacific Atlantic Water Flow (LC 417)
All Paths From Source to Target (LC 797)

Interview tip: The most common DFS mistake in interviews is forgetting to mark nodes as visited before recursing — leading to infinite loops in graphs with cycles. Always set visited[node] = true at the start of the call, before processing neighbors. Draw this out for the interviewer.

Dijkstra's Algorithm

Shortest path in weighted graphs with non-negative edges

Data structure

Min-heap (priority queue)

Complexity

O((V + E) log V) time, O(V) space

Use when:

The graph has weighted edges and all weights are non-negative
You need the shortest distance from a source to all other nodes (or to a specific target)
You need to optimize a path by minimizing total cost, time, or distance

Don't use when:

The graph has negative edge weights — Dijkstra's greedy assumption breaks down. Use Bellman-Ford for negative weights.

Classic interview problems:

Network Delay Time (LC 743)
Path With Minimum Effort (LC 1631)
Cheapest Flights Within K Stops (LC 787)
Find the City With the Smallest Number of Neighbors at a Threshold Distance (LC 1334)
Swim in Rising Water (LC 778)

Interview tip: The Dijkstra pattern is always the same: push (cost, node) to the heap → pop the cheapest → skip if already visited → process neighbors and push updated costs. Know O((V+E) log V) and be able to explain why the log V factor comes from heap operations. Mentioning Bellman-Ford for negative weights as a follow-up earns extra points.

The decision framework: which algorithm to use

When you see a graph problem in an interview, run through this decision tree before writing a single line of code. Verbalizing this process shows structured thinking — which is often more valuable to interviewers than the implementation itself.

Signal → Algorithm → Reason

Unweighted graph, need shortest path	BFS	BFS expands level by level — first time you reach a node is via shortest path
Need minimum number of steps / hops	BFS	'Steps' = edges = unweighted. BFS counts layers.
Weighted graph, all weights ≥ 0	Dijkstra	Greedy expansion via min-heap always finds optimal cost
Weighted graph with negative edges	Bellman-Ford	Dijkstra's greedy assumption breaks with negative weights
Cycle detection	DFS	Track visited + in-stack state during DFS traversal
All paths, not just shortest	DFS + backtracking	BFS doesn't enumerate all paths — DFS explores every branch
Connected components / flood fill	DFS or BFS	Either works — DFS is simpler to implement recursively
Topological sort (dependency ordering)	DFS or Kahn's BFS	DFS post-order gives reverse topological order; Kahn's uses in-degree BFS
Process nodes level by level (tree or graph)	BFS	Queue naturally processes all nodes at depth k before depth k+1

The question to ask first

Before choosing an algorithm, ask: "Does the graph have weights?" If no → choose between BFS and DFS based on what the problem needs (shortest path vs. full exploration). If yes → use Dijkstra (non-negative) or Bellman-Ford (negative weights). This single question narrows the decision from three options to two in almost every case.

What interviewers actually look for in graph problems

Interviewers at senior levels are rarely testing whether you can implement BFS from scratch. They're testing whether you can reason about graph problems systematically. These are the behaviors that distinguish strong from average candidates:

Clarifying the graph structure before coding. Is it directed or undirected? Weighted or unweighted? Can there be cycles? Does it have a single source or multiple sources? These questions change the algorithm. Asking them shows you're not pattern-matching blindly.
Explaining why you chose the algorithm, not just what it is. "I'm using BFS because the graph is unweighted and I need the minimum number of steps" is a complete answer. "I'll use BFS" is not. The reasoning is what the interviewer is evaluating.
Identifying the graph implicitly. Many graph problems don't say "graph" — they present a grid, a word transformation, a dependency list, or a city network. Recognizing that these are graph problems is itself a skill. Rotting Oranges is a multi-source BFS. Word Ladder is an unweighted shortest-path problem on an implicit graph.
Handling edge cases out loud. What if the graph is disconnected? What if the source equals the target? What if there are no edges? Bringing up edge cases proactively — even briefly — signals engineering maturity.
Knowing the complexity without being asked. O(V + E) for BFS and DFS, O((V + E) log V) for Dijkstra. Being able to derive these (not just recite them) is the difference between passing and failing the follow-up questions at top companies.

How to study graph algorithms so they actually stick

The reason graph algorithms feel slippery is that most resources explain them in isolation — here's how BFS works, here's how DFS works — without building the mental model of when to choose each one. The study approach that works is different:

Watch the execution before writing code. For BFS, watch the queue grow and shrink level by level. For Dijkstra, watch the min-heap pop nodes in cost order and the distance table update. For DFS, watch the call stack grow and unwind. This visual step builds the mental model that makes implementation feel natural, not mechanical.
Implement each algorithm on the same graph. Take a 5-node, 7-edge graph. Run BFS on it, then DFS, then Dijkstra (with weights). Seeing three different traversal orders on the same graph makes the differences concrete, not abstract.
Build the decision reflex, not the recall reflex. After solving each problem, write one sentence: "This is BFS because the graph is unweighted and I need shortest path." Train the recognition, not just the implementation. In an interview, you'll have 5 minutes to identify the approach — that sentence is what you're building toward.
Practice on grid problems. A 2D grid is a graph where each cell is a node and each adjacent cell is an edge. Grid problems are the most common disguised graph problems in interviews. Practice BFS flood fill, multi-source BFS, and DFS path exploration on grids — the pattern transfers directly.

Frequently asked questions

When should I use BFS vs DFS in a coding interview?

Use BFS when you need the shortest path in an unweighted graph or the minimum number of steps to reach a target. Use DFS when you need to explore all paths, detect cycles, check connectivity, or solve backtracking problems. If shortest path is not required, both can work — DFS is often simpler to implement recursively.

What is the difference between BFS and Dijkstra?

BFS finds the shortest path in terms of number of edges (unweighted graphs), treating every edge as cost 1. Dijkstra finds the shortest path by total weight (weighted graphs), using a min-heap to always expand the lowest-cost node first. Use BFS for "minimum hops" and Dijkstra for "minimum cost."

Can DFS find the shortest path in a graph?

No — DFS does not guarantee the shortest path. It finds a path, but it may not be the shortest one. To find the shortest path in an unweighted graph, use BFS. To find the shortest path in a weighted graph with non-negative edges, use Dijkstra.

What is the time complexity of BFS and DFS?

Both BFS and DFS have O(V + E) time complexity, where V is the number of vertices and E is the number of edges. Each node is visited once and each edge is traversed once. Space complexity is O(V) for the queue (BFS) or call stack (DFS).

What graph algorithm should I use if the graph has negative weights?

Dijkstra does not work with negative edge weights because its greedy assumption — that once a node is visited it has been reached via the shortest path — breaks down. Use Bellman-Ford instead, which runs in O(V × E) and handles negative weights correctly. Mentioning this distinction in an interview is a strong positive signal.

Summary

BFS, DFS, and Dijkstra cover the structural foundation of graph interview problems. The key to using them correctly is not memorizing implementations — it's building the decision reflex: unweighted + shortest path → BFS; weighted + non-negative → Dijkstra; exhaustive exploration, cycle detection, or backtracking → DFS.

In an interview, the algorithm you choose matters less than being able to articulate why you chose it. Practice that reasoning alongside the implementation. That's what separates candidates who understand graphs from candidates who've memorized them.

Explore more

Interactive algorithm visualizer →Watch BFS, DFS, and Dijkstra run step by step on real graphs
The 7 algorithm patterns that cover 80% of coding interview problems →Decision framework for all patterns, not just graphs
Coding interview prep →Roadmaps and visual debuggers organized by pattern
Dynamic programming explained visually →Memoization, tabulation, and the 5 DP patterns for interviews

See BFS, DFS, and Dijkstra run in real time

Expora's visual debuggers show you exactly what happens inside each algorithm — node by node, step by step, with your own code. Build the mental model that makes graph problems systematic, not stressful.