Graphs: BFS and DFS

1The mental model (what this really is)#

A graph is just nodes connected by edges. That is the whole thing.

• A node might be a city, a person, a cell in a grid, or a string.
• An edge is any relationship: a road, a friendship, "these two cells touch," "these two words differ by one letter."
• BFS and DFS both walk every reachable node from a start, without visiting anyone twice. They only differ in the order, and that order is the whole game.

BFS (breadth-first) spreads out in rings.

• Visit everything one step away, then two steps, then three. Drop a stone in water: the ripple reaches all the close things before any far thing.
• That ring-by-ring order is why BFS finds the shortest number of steps. The first time you touch the goal, you got there in the fewest hops, guaranteed, because every closer node was already checked and none of them was it.

DFS (depth-first) picks a direction and runs with it.

• Go until you hit a wall, then back up and try the next direction. Explore a cave by always taking the next tunnel, turning back only at a dead end.
• DFS goes deep first, not wide. It finds a path fast, but it has no reason to find the shortest one.

2How to recognize it (the signals in a problem)#

The first skill is seeing the graph. Most interview problems never say the word.

• They hand you a 2D grid, a list of word pairs, a set of course prerequisites, a map of flights.
• Train the reflex: the moment you read the prompt, ask what are my nodes and what counts as an edge.
• Answer those two and the rest is template.

Reach for BFS when:

• The question asks for the shortest path or fewest steps in an unweighted graph. "Minimum moves," "least number of transformations," "shortest distance." That phrasing is a BFS flare in the sky.
• Unweighted means every edge costs 1. The second edge weights differ, BFS is wrong and you want Dijkstra.
• You want to process things in levels. "How many rounds until everything is infected," or anything where distance-from-start is the answer you report.

Reach for DFS when:

• You just need to visit everything or find connected pieces. Counting islands, flood fill, finding groups. The answer is a count or a yes/no, not a distance.
• The problem is naturally recursive: explore a path, make a choice, go deeper, back out. Cycle detection, topological sort, path-exists questions.

My tiebreaker rule.

• If either would technically work and all you need is "can I reach it" or "how many components," pick DFS. It is three fewer lines and nothing to get wrong with queue levels.
• If the answer is a distance or a minimum, pick BFS and do not argue with it.

3The template (how it works, with pseudocode)#

Both algorithms need the same three ingredients:

• A starting node.
• A visited set so you never loop forever.
• A way to get a node's neighbors.

The only real structural difference is the data structure. BFS uses a queue (first in, first out). DFS uses a stack (last in, first out), either explicit or the call stack via recursion. Swap the container, swap the order.

BFS, iterative with a queue:

function bfs(start):
  visited = {start}
  queue = [start]
  steps = 0
  while queue is not empty:
    for each node in current queue level:   # one ring
      node = queue.pop_front()
      if node is the goal: return steps
      for neighbor in neighbors(node):
        if neighbor not in visited:
          visited.add(neighbor)
          queue.push_back(neighbor)
    steps += 1

• That inner "for each node in current level" loop is the trick for level-by-level BFS.
• Snapshot the queue size before the loop (say it holds 5 nodes), pop exactly those 5, and everything you add during the pass belongs to the next ring.
• Only after the ring is fully drained do you run steps += 1.
• Get comfortable with this snapshot. It separates people who understand BFS from people who memorized it, and interviewers can tell which one you are within seconds.

DFS, recursive:

function dfs(node, visited):
  if node in visited: return
  visited.add(node)
  # do work here (count it, record it, etc.)
  for neighbor in neighbors(node):
    dfs(neighbor, visited)

DFS, iterative with an explicit stack (use this when recursion might blow the stack):

function dfs(start):
  visited = set()
  stack = [start]
  while stack is not empty:
    node = stack.pop()
    if node in visited: continue
    visited.add(node)
    for neighbor in neighbors(node):
      if neighbor not in visited:
        stack.push(neighbor)

• Swapping the queue for a stack is the entire structural change. Same skeleton, different order.
• Write one and you can write the other by changing pop_front to pop.

4A worked example (walk through one problem step by step)#

Take a classic: Number of Islands (LeetCode 200, one of the most-asked grid questions at Amazon).

• You get a grid of 1s (land) and 0s (water). Count how many separate islands exist.
• Land connects horizontally and vertically, not diagonally.

First, see the graph.

• Each land cell is a node.
• Two land cells share an edge if they are directly next to each other (up, down, left, right).
• An island is a connected component.
• "Count connected components" means: walk the whole grid, and every time you find unvisited land, that is a new island, so flood the entire thing to avoid counting any of its cells again.

I use DFS because I only need to count groups. Here is the shape of it:

count = 0
for each cell (r, c) in grid:
  if grid[r][c] == 1 and (r,c) not visited:
    count += 1
    flood(r, c)        # DFS that marks this whole island visited
return count

function flood(r, c):
  if out of bounds or grid[r][c] == 0 or (r,c) visited: return
  mark (r,c) visited
  flood(r+1, c); flood(r-1, c); flood(r, c+1); flood(r, c-1)

• The bounds-and-water guard is the first line of flood. Every recursive call is safe before it ever indexes the grid. That ordering kills most grid bugs.

Walk it on a tiny grid:

1 1 0
0 1 0
0 0 1

• Hit (0,0): land, unvisited. New island. count = 1. Flood marks (0,0), then (0,1) to the right, then down to (1,1). From (1,1) every direction is water or already visited. The top-left blob is now marked.
• Keep scanning: (0,2) water, (1,0) water, (1,1) already handled, rest of row 1 water. Row 2: (2,0), (2,1) water.
• Hit (2,2): land, unvisited. New island. count = 2. Flood it: alone, nothing adjacent, done.
• Scan finishes. Answer: 2.

Why this generalizes.

• The grid IS the graph. The four direction calls ARE the edges.
• Internalize that translation and Flood Fill, Surrounded Regions, and Max Area of Island all feel like the same problem wearing different clothes.
• If an interviewer asks for BFS instead, the outer scan is unchanged: just make flood push neighbors onto a queue instead of recursing.

5Variations and gotchas#

Multi-source BFS.

• Seed the queue with several starts at once, all at distance 0, instead of one. Rotting Oranges and Walls and Gates are the famous ones.
• Everything spreads outward in sync, so the distance you compute is distance to the nearest source for free.
• The aha: if you think "shortest distance from the nearest of many sources," push them all in before the loop starts.
• Running a separate BFS from each source and taking the min is O(sources * (V+E)) and times out on the large cases.

BFS on a grid for shortest path.

• "Fewest steps through a maze" on an unweighted grid: BFS gives the answer directly in O(R*C).
• Do not reach for Dijkstra. It carries a heap and a log factor, and pulling it out here tells the interviewer you do not know the difference.
• Save Dijkstra for the day the maze cells cost different amounts to enter.

DFS for cycle detection.

• In a directed graph, track three states per node: unvisited, in-progress (on the current recursion path), and done.
• Reach an in-progress node and you found a cycle (a back edge). Reach only done nodes and there is no cycle through there.
• This 3-color trick powers Course Schedule and underpins topological sort.
• In an undirected graph the rule is simpler: a cycle exists if you reach a visited node that is not the parent you came from.

Topological sort.

• Two ways: DFS post-order reversed, or BFS with in-degrees (Kahn's algorithm).
• Kahn's is my default in interviews because it detects a cycle naturally: finish with fewer than V nodes in the output and a cycle blocked the rest.
• Any "order of tasks with dependencies" problem is this: build order, course order, package install order.

Recursion depth.

• On a huge grid or a long chain, recursive DFS can overflow the call stack.
• In Python the default recursion limit is around 1000, so a single path of a few thousand nodes crashes with a RecursionError.
• Name this risk out loud and switch to the iterative stack version. Flagging the failure mode before it bites scores real points with senior interviewers.

Disconnected graphs.

• One traversal from a single node only reaches that node's component.
• If the graph might be in pieces, loop over all nodes and launch a fresh traversal from each unvisited one, exactly what the outer scan in Number of Islands does.
• Forget this and you get wrong component counts. It is a classic silent failure because the code runs fine on the connected test case.

6Complexity#

For a graph with V nodes and E edges:

• Both BFS and DFS run in O(V + E) time. You touch each node once and each edge at most twice (once from each endpoint).
• That is as fast as it gets for visiting everything. You cannot count all the nodes and edges in less time than it takes to look at them.
• Space is O(V) for the visited set.

On top of the visited set:

• BFS queue can hold up to O(V) nodes. One wide level holds a large fraction of the graph at once. Picture a star with one center and a million leaves: expand the center and all million leaves sit in the queue together.
• DFS stack (call stack or explicit) is O(V) in the worst case, the length of the longest path. A single long chain of V nodes stacks V frames deep.

For a grid with R rows and C columns:

• Think of it as V = R*C nodes and roughly 4*R*C edges, so O(R*C) time and O(R*C) space. Clean and linear.
• When asked for complexity, give it in R and C for a grid, not V and E, because that is the language of the problem in front of you.

7Mistakes that cost people the round#

Not marking visited, or marking it too late.

• Infinite loops in a cyclic graph, or exponential blowup through re-queued nodes.
• For BFS, mark on enqueue. I said it in section 3 and I will say it again: it fails more real interviews than any other single thing.

Using DFS when the problem wants shortest path.

• DFS finds a path, not the shortest one in an unweighted graph.
• If the question says "fewest" or "minimum steps," DFS returns wrong answers on a lot of cases, and the interviewer has a counterexample ready. Match the tool to the word.

Missing the level boundary in BFS.

• If you need the distance, count rings correctly with the snapshot-the-queue-size trick.
• People increment the step counter once per node instead of once per level and report numbers off by a factor of the branching width.
• Drain the whole ring, then add 1.

Forgetting disconnected components.

• Running one traversal and reporting a count when the graph has islands you never reached.
• The outer loop over all nodes is cheap insurance.

Mutating the grid as your visited set without saying so.

• Setting land to 0 as you flood it is a fine trick, and it saves the O(R*C) visited set.
• But if the interviewer needs the grid intact afterward, you just destroyed their input.
• One sentence of "is it okay if I mutate the input?" turns a risky move into a thoughtful one.

Off-by-one and bounds on grids.

• Half the bugs in grid DFS are a missing bounds check before you index.
• Put the out-of-bounds guard at the very top of the recursive function, before any grid[r][c] access, so every entry into the function is safe.

Want to know which rounds at a specific company lean on graph traversal? Check the company guides to see where this pattern shows up.