Graphs, BFS and DFS Explained (for Interviews)

A graph is a set of nodes connected by edges, and the two ways to explore one are BFS (breadth-first, level by level, with a queue) and DFS (depth-first, as deep as possible, with recursion or a stack). Graphs model relationships — maps, social networks, dependencies — and graph traversal is one of the highest-value patterns in coding interviews because so many problems are graphs in disguise.

Once you can represent a graph and write BFS and DFS from memory, a large class of “find the path / count the groups / order the tasks” problems opens up.

Representing a graph

The most common representation in interviews is an adjacency list — a map from each node to its neighbours:

// Undirected graph: A–B, A–C, B–D
const graph = {
  A: ["B", "C"],
  B: ["A", "D"],
  C: ["A"],
  D: ["B"],
};

The alternative, an adjacency matrix (a 2D grid of true/false), is simpler but uses O(V²) space. Use an adjacency list unless the graph is dense.

DFS — go deep

Depth-first search follows one path to its end, then backtracks. It’s naturally recursive (the call stack is the stack), and needs a visited set to avoid looping on cycles:

function dfs(node, graph, visited = new Set()) {
  if (visited.has(node)) return;
  visited.add(node);
  visit(node);
  for (const neighbor of graph[node]) {
    dfs(neighbor, graph, visited);
  }
}

Use DFS for exhaustive exploration, cycle detection, connected components, and topological sorting.

BFS — go wide

Breadth-first search visits all immediate neighbours first, then their neighbours, rippling outward. It uses a queue, and it finds the shortest path in an unweighted graph because it reaches every node by the fewest edges:

function bfs(start, graph) {
  const visited = new Set([start]);
  const queue = [start];
  while (queue.length) {
    const node = queue.shift();
    visit(node);
    for (const neighbor of graph[node]) {
      if (!visited.has(neighbor)) {
        visited.add(neighbor);
        queue.push(neighbor);
      }
    }
  }
}

BFS vs DFS — which to use

Both touch every node and edge once, so both are O(V + E). The choice is about what you need, not speed.

Problems that are secretly graphs

Many interview problems don’t look like graphs until you reframe them:

• Number of islands — a grid where adjacent land cells are connected → count connected components with DFS/BFS.
• Shortest path in a maze → BFS on a grid.
• Course schedule / build order → detect a cycle and topologically sort a dependency graph (DFS).
• Word ladder — words are nodes, one-letter changes are edges → BFS for the shortest transformation.

Recognising the graph underneath is the real skill; the traversal code is the same every time.

Beyond unweighted graphs

When edges have weights (distances, costs), plain BFS no longer gives the shortest path. You need:

• Dijkstra’s algorithm — shortest path with non-negative weights (a priority queue / heap).
• Union-Find (disjoint set) — fast connectivity and cycle detection.

These are more advanced and appear in senior/staff interviews.

Common mistakes

• Forgetting the visited set → infinite loops on cyclic graphs. This is the #1 graph bug.
• Using DFS for shortest path in an unweighted graph — it finds a path, not the shortest. Use BFS.
• Marking visited too late in BFS — mark a node when you enqueue it, not when you dequeue it, or you’ll add duplicates.
• Using plain BFS on a weighted graph — reach for Dijkstra instead.

Where this fits

Graphs are Phase 2 of the coding interview roadmap, built on trees (a tree is an acyclic graph) and the queue and stack structures BFS and DFS run on.

BFS, DFS, and the “this is secretly a graph” reframings are drawn out with diagrams in our job-ready tier — JavaScript in Three Months, Python in Three Months, and Java in Three Months. For Dijkstra, union-find, topological sort, and the weighted-graph algorithms that come up in senior and staff rounds, the for Staff Engineers tier goes deeper: JavaScript, Python, Java.

Learn to spot the graph, carry a visited set, and pick BFS or DFS by what you need — that’s most of graph interviewing.