← Index

Graphs

BFS & DFS

The two ways to walk a graph or tree — level by level, or all the way down first.

What it is

Breadth-First Search explores all neighbors before going deeper, using a queue — it's the one that finds the shortest path in an unweighted graph, because it reaches every node in order of distance. Depth-First Search commits to one path and backtracks only when stuck, using a stack (or recursion, which is an implicit stack) — it's the natural fit for 'explore all possibilities' problems.

Real-world examples

• BFS: ripples spreading out from a stone dropped in water — everything at distance 1 lights up before anything at distance 2.
• DFS: solving a maze by picking a direction and following it until you hit a dead end, then backtracking to the last fork.

Where you've probably used this already

• 'Degrees of separation' / shortest-hop features (LinkedIn's '2nd degree connection') — BFS.
• Recursively walking a directory tree, or a component tree, until you hit leaves — DFS.
• Detecting cycles in a dependency graph, or topologically sorting build steps so each runs after its dependencies — DFS-based.

Complexity

Code

// BFS & DFS — the two ways to walk a graph or tree.
//
// DFS (Depth-First): go as far down one path as possible, backtrack when
// stuck. Uses a STACK (or recursion, which is just an implicit stack).
//
// BFS (Breadth-First): explore all neighbors first, then their neighbors.
// Uses a QUEUE. Finds the SHORTEST path in an unweighted graph.

const graph = {
  A: ["B", "C"],
  B: ["A", "D"],
  C: ["A", "E"],
  D: ["B", "E"],
  E: ["C", "D", "F"],
  F: ["E"],
};

// --- DFS, recursive ---
function dfs(start, visited = new Set(), order = []) {
  visited.add(start);
  order.push(start);
  for (const neighbor of graph[start]) {
    if (!visited.has(neighbor)) dfs(neighbor, visited, order);
  }
  return order;
}

// --- DFS, iterative (explicit stack — same idea, no call stack limit) ---
function dfsIterative(start) {
  const visited = new Set([start]);
  const stack = [start];
  const order = [];

  while (stack.length) {
    const node = stack.pop();
    order.push(node);
    for (const neighbor of graph[node]) {
      if (!visited.has(neighbor)) {
        visited.add(neighbor);
        stack.push(neighbor);
      }
    }
  }
  return order;
}

// --- BFS, iterative (queue) ---
function bfs(start) {
  const visited = new Set([start]);
  const queue = [start];
  const order = [];

  while (queue.length) {
    const node = queue.shift();
    order.push(node);
    for (const neighbor of graph[node]) {
      if (!visited.has(neighbor)) {
        visited.add(neighbor);
        queue.push(neighbor);
      }
    }
  }
  return order;
}

// --- Example Usage ---
console.log("DFS (recursive):", dfs("A"));       // A, B, D, E, C, F
console.log("DFS (iterative):", dfsIterative("A")); // A, C, E, F, D, B (order differs — stack pops last-pushed)
console.log("BFS:", bfs("A"));                    // A, B, C, D, E, F (level by level)

// Real uses:
// - BFS: "shortest number of clicks/hops" (social network degrees of
//   separation, shortest route with equal-weight roads)
// - DFS: exploring all possibilities before committing (maze solving,
//   detecting cycles, dependency resolution / topological sort)
// - both are literally how document.querySelectorAll-style DOM walks
//   and directory recursion (fs.readdir recursively) work