BFS vs DFS: Differences, Examples in JavaScript & Python, When to Use Each

// Adjacency list: each node maps to the nodes it points to
export const graph = {
  A: ["B", "C"],
  B: ["D", "E"],
  C: ["F"],
  D: [],
  E: ["F"],
  F: [],
};

      A
     / \
    B   C
   / \   \
  D   E → F      (E and C both point to F)

BFS from A: A B C D E F   (level by level)
DFS from A: A B D E F C   (one branch to the bottom, then back up)

// Breadth-first search: visit nodes level by level
export function bfs(graph, start) {
  const visited = new Set([start]);
  const queue = [start];
  const order = [];

  // Read with an index instead of queue.shift(), which is O(n) per call
  for (let head = 0; head < queue.length; head++) {
    const node = queue[head];
    order.push(node);
    for (const next of graph[node] ?? []) {
      if (!visited.has(next)) {
        visited.add(next); // mark when queued, so nothing is queued twice
        queue.push(next);
      }
    }
  }
  return order;
}

import { graph } from "./graph.js";
import { bfs } from "./bfs.js";

console.log(bfs(graph, "A")); // ["A", "B", "C", "D", "E", "F"]

// A common version (including an older copy of this article):
while (queue.length > 0) {
  const node = queue.shift();       // O(n): moves every remaining item
  if (!visited.has(node)) {
    visited.add(node);              // marked only when dequeued...
    queue.push(...graph[node]);     // ...so F gets queued twice
  }
}

// Fewest-edges path from start to goal (unweighted graph), or null
export function shortestPath(graph, start, goal) {
  const parent = new Map([[start, null]]);
  const queue = [start];

  for (let head = 0; head < queue.length; head++) {
    const node = queue[head];
    if (node === goal) {
      const path = [];
      for (let at = goal; at !== null; at = parent.get(at)) path.push(at);
      return path.reverse();
    }
    for (const next of graph[node] ?? []) {
      if (!parent.has(next)) {
        parent.set(next, node);
        queue.push(next);
      }
    }
  }
  return null; // goal can't be reached
}

shortestPath(graph, "A", "F"); // ["A", "C", "F"]  (2 edges; A→B→E→F is 3)
shortestPath(graph, "D", "A"); // null  (edges only go one way)

// Fewest steps through a maze: "#" is a wall, moves are up/down/left/right
export function mazeSteps(maze, [startRow, startCol], [endRow, endCol]) {
  const rows = maze.length;
  const cols = maze[0].length;
  const seen = new Set([`${startRow},${startCol}`]);
  const queue = [[startRow, startCol, 0]];

  for (let head = 0; head < queue.length; head++) {
    const [r, c, steps] = queue[head];
    if (r === endRow && c === endCol) return steps;
    for (const [dr, dc] of [[1, 0], [-1, 0], [0, 1], [0, -1]]) {
      const nr = r + dr;
      const nc = c + dc;
      const key = `${nr},${nc}`;
      if (nr < 0 || nc < 0 || nr >= rows || nc >= cols) continue;
      if (maze[nr][nc] === "#" || seen.has(key)) continue;
      seen.add(key);
      queue.push([nr, nc, steps + 1]);
    }
  }
  return -1; // no way through
}

const maze = [
  "S..#....",
  ".#.#.##.",
  ".#...#..",
  ".####.#.",
  "......#E",
];
mazeSteps(maze, [0, 0], [4, 7]);          // 15
mazeSteps(["S#", "#E"], [0, 0], [1, 1]);  // -1 (walled off)

// Depth-first search, recursive: short and clear, but limited by the call stack
export function dfsRecursive(graph, node, visited = new Set(), order = []) {
  visited.add(node);
  order.push(node);
  for (const next of graph[node] ?? []) {
    if (!visited.has(next)) dfsRecursive(graph, next, visited, order);
  }
  return order;
}

// Depth-first search with an explicit stack: same order, no recursion limit
export function dfs(graph, start) {
  const visited = new Set();
  const stack = [start];
  const order = [];

  while (stack.length > 0) {
    const node = stack.pop();
    if (visited.has(node)) continue;
    visited.add(node);
    order.push(node);
    // Push in reverse so the first neighbor is explored first
    const neighbors = graph[node] ?? [];
    for (let i = neighbors.length - 1; i >= 0; i--) {
      if (!visited.has(neighbors[i])) stack.push(neighbors[i]);
    }
  }
  return order;
}

dfs(graph, "A");          // ["A", "B", "D", "E", "F", "C"]
dfsRecursive(graph, "A"); // ["A", "B", "D", "E", "F", "C"]

// Cycle detection in a directed graph with DFS.
// "visiting" = on the current path; reaching it again means a cycle.
export function hasCycle(graph) {
  const state = new Map(); // node -> "visiting" | "done"

  function visit(node) {
    if (state.get(node) === "visiting") return true;
    if (state.get(node) === "done") return false;
    state.set(node, "visiting");
    for (const next of graph[node] ?? []) {
      if (visit(next)) return true;
    }
    state.set(node, "done");
    return false;
  }

  return Object.keys(graph).some((node) => visit(node));
}

hasCycle(graph);                  // false
hasCycle({ ...graph, F: ["B"] });  // true: B → E → F → B

from collections import deque

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


def bfs(graph, start):
    visited = {start}
    queue = deque([start])  # popleft() is O(1); list.pop(0) is O(n)
    order = []
    while queue:
        node = queue.popleft()
        order.append(node)
        for nxt in graph.get(node, []):
            if nxt not in visited:
                visited.add(nxt)
                queue.append(nxt)
    return order


def dfs(graph, start):
    visited = set()
    stack = [start]
    order = []
    while stack:
        node = stack.pop()
        if node in visited:
            continue
        visited.add(node)
        order.append(node)
        for nxt in reversed(graph.get(node, [])):
            if nxt not in visited:
                stack.append(nxt)
    return order


def dfs_recursive(graph, node, visited=None):
    if visited is None:  # never use visited=set() as a default
        visited = set()
    visited.add(node)
    order = [node]
    for nxt in graph.get(node, []):
        if nxt not in visited:
            order += dfs_recursive(graph, nxt, visited)
    return order


print(bfs(graph, "A"))            # ['A', 'B', 'C', 'D', 'E', 'F']
print(dfs(graph, "A"))            # ['A', 'B', 'D', 'E', 'F', 'C']
print(dfs_recursive(graph, "A"))  # ['A', 'B', 'D', 'E', 'F', 'C']

# Don't do this: the default set is created once and shared by every call
def dfs(graph, node, visited=set()):
    ...

dfs(graph, "A")  # prints A B D E F C
dfs(graph, "A")  # prints nothing: every node is already "visited"