Level 2 · 45 min

Graphs: BFS, DFS, and the Shape of the Frontier

Graphs model relationships: services calling services, users connected to users, states connected by valid transitions. The senior skill is choosing the traversal that matches the question, then making visited-state explicit.

Represent the graph before traversing it

An adjacency list is usually the default for sparse graphs because it stores only real edges. An adjacency matrix gives constant-time edge checks but costs n squared space. For interviews and production systems, start by naming vertices, edge direction, edge weight, and whether the graph can contain cycles.

BFS explores by distance

Breadth-first search uses a queue and processes the frontier level by level. In an unweighted graph, the first time BFS reaches a node is the shortest path in number of edges. This is why BFS fits shortest path in a social graph, minimum moves in a puzzle, or dependency distance.

DFS explores by commitment

Depth-first search uses recursion or an explicit stack. It fits reachability, connected components, cycle detection, topological ordering, and backtracking. The bug pattern is marking visited too late: in cyclic graphs, mark when a node enters the stack or queue, not after all neighbors finish.

Key Takeaways

BFS answers shortest unweighted distance because it expands one edge farther per level.
DFS answers structure questions: components, cycles, ordering, and exhaustive search.
Visited state is part of the algorithm, not a detail; incorrect timing creates infinite loops or duplicate work.

Code example

function bfs(start):
  queue = [start]
  visited = set(start)
  distance[start] = 0
  while queue is not empty:
    node = queue.pop_front()
    for next in graph[node]:
      if next not in visited:
        visited.add(next)
        distance[next] = distance[node] + 1
        queue.push_back(next)