BFS vs DFS Explained

BFS (Breadth-First Search) and DFS (Depth-First Search) are the two fundamental graph/tree traversal algorithms. Choosing the right one depends on the problem : and interviewers expect you to explain why.

BFS : Breadth-First Search

Explores all neighbors at the current depth before moving to the next level. Uses a queue. Guarantees the shortest path in unweighted graphs.

function bfs(graph: Map<number, number[]>, start: number): number[] {
  const visited = new Set<number>();
  const queue = [start];
  const result: number[] = [];
  visited.add(start);
  while (queue.length) {
    const node = queue.shift()!;
    result.push(node);
    for (const neighbor of graph.get(node) || []) {
      if (!visited.has(neighbor)) {
        visited.add(neighbor);
        queue.push(neighbor);
      }
    }
  }
  return result;
}

DFS : Depth-First Search

Explores as far as possible along each branch before backtracking. Uses a stack (or recursion). Uses less memory than BFS for wide graphs.

function dfs(graph: Map<number, number[]>, start: number): number[] {
  const visited = new Set<number>();
  const result: number[] = [];
  function explore(node: number) {
    visited.add(node);
    result.push(node);
    for (const neighbor of graph.get(node) || []) {
      if (!visited.has(neighbor)) explore(neighbor);
    }
  }
  explore(start);
  return result;
}

BFS visits level by level: 1, 2, 3, 4, 5, 6, 7. DFS goes deep first: 1, 2, 4, 5, 3, 6, 7.

graph TD
    A((1)) --> B((2))
    A --> C((3))
    B --> D((4))
    B --> E((5))
    C --> F((6))
    C --> G((7))
    
    style A fill:#D97A2B,stroke:#B86418,color:#fff
    style B fill:#D97A2B,stroke:#B86418,color:#fff
    style D fill:#D97A2B,stroke:#B86418,color:#fff
    style C fill:#FAF6EE,stroke:#E8DFC8
    style E fill:#FAF6EE,stroke:#E8DFC8
    style F fill:#FAF6EE,stroke:#E8DFC8
    style G fill:#FAF6EE,stroke:#E8DFC8

When to Use Which

Time and Space Complexity

Common Mistakes

• Using BFS for topological sort : BFS (Kahn's algorithm) works, but DFS is more natural and commonly expected.
• Using DFS for shortest path : DFS does not guarantee the shortest path in unweighted graphs.
• Forgetting the visited set : without it, both BFS and DFS loop infinitely on cycles.
• Confusing BFS with level-order : BFS is the algorithm; level-order is a specific application on trees.
• Not handling disconnected components : iterate over all nodes and start BFS/DFS on each unvisited node.