What is BFS (Breadth First Search)?

• Breadth-First Search (BFS) is a graph traversal that explores all vertices at the current distance before moving one step farther.
• Queue processes vertices in discovery order, enforcing the level-by-level expansion.
• Visited set prevents revisiting and stops cycles from causing infinite loops.
• Shortest path in an unweighted graph is guaranteed because BFS reaches each node by the fewest hops first.
• Time is O(V + E); space is O(V) for the queue and visited set.

What is BFS?

Breadth-First Search is a graph and tree traversal that explores all vertices at the current distance from the source before moving to vertices one step farther away. It uses a queue to maintain the processing order and a visited set to prevent revisiting nodes. Because it expands outward level by level, BFS naturally finds the shortest path in terms of number of edges in an unweighted graph.

package com.bank.service;

import java.util.*;

public class FraudNetworkScanner {
    // BFS: find all accounts reachable from a suspect
    public List<String> bfs(Map<String, List<String>> graph,
                            String source) {
        List<String> visited = new ArrayList<>();
        Set<String> seen = new HashSet<>();
        Queue<String> queue = new LinkedList<>();
        queue.offer(source);
        seen.add(source);
        while (!queue.isEmpty()) {
            String current = queue.poll();
            visited.add(current);
            for (String neighbor : graph.getOrDefault(
                    current, Collections.emptyList())) {
                if (seen.add(neighbor)) {
                    queue.offer(neighbor);
                }
            }
        }
        return visited;
    }
}

Why does BFS guarantee shortest paths in unweighted graphs?

The queue enforces a strict ordering: every vertex at distance d is enqueued before any vertex at distance d+1 is processed. This means the first time BFS reaches any vertex, it has reached it by the fewest possible edges. Once a vertex is visited, later paths to it cannot be shorter, so they are safely ignored.

Graph:  A --- B --- D
        |         |
        C --- E ---+

BFS from A:
  Level 0: [A]
  Level 1: [B, C]  (direct neighbors of A)
  Level 2: [D, E]  (neighbors of B and C)

Shortest path A→D = 2 hops (A→B→D)

How does the visited set prevent infinite loops?

In a graph with cycles, a node can be reached from multiple directions. Without a visited set, the algorithm would enqueue the same node multiple times and loop forever. The visited set ensures each node is processed exactly once.

// Neat trick: visited.add() returns false if already present
if (seen.add(neighbor)) {  // checks AND marks in one step
    queue.offer(neighbor);
}

How do you reconstruct the actual shortest path?

Store a parent pointer for each vertex when you first discover it. Then trace back from the destination to the source using the parent map to get the shortest path.

public List<String> shortestPath(
        Map<String, List<String>> graph,
        String source, String dest) {
    Map<String, String> parent = new HashMap<>();
    Queue<String> queue = new LinkedList<>();
    queue.offer(source);
    parent.put(source, null);
    while (!queue.isEmpty()) {
        String current = queue.poll();
        if (current.equals(dest)) break;
        for (String nb : graph.getOrDefault(
                current, Collections.emptyList())) {
            if (!parent.containsKey(nb)) {
                parent.put(nb, current);
                queue.offer(nb);
            }
        }
    }
    // Reconstruct path from dest to source
    List<String> path = new ArrayList<>();
    for (String at = dest; at != null; at = parent.get(at)) {
        path.add(at);
    }
    Collections.reverse(path);
    return path;
}

How is BFS different from DFS?

BFS explores breadth-first (ring by ring); DFS explores depth-first (as deep as possible before backtracking). BFS finds shortest paths in unweighted graphs; DFS does not. BFS uses a queue; DFS uses a stack (or recursion).

| Aspect | BFS | DFS |
|--------|-----|-----|
| Data structure | Queue | Stack / recursion |
| Exploration order | Level by level | Deep then backtrack |
| Shortest path | Yes (unweighted) | No |
| Memory | O(V) can be large for wide graphs | O(h) where h is depth |
| Use cases | Shortest path, level-order | Connected components, cycle detection |

When should you use BFS vs Dijkstra?

BFS works only when all edges have the same weight (or no weight). When edges have different weights (like different transaction fees), BFS cannot find the lowest-cost path because it only counts hops, not cumulative cost. Dijkstra's algorithm handles weighted edges by always expanding the lowest-cost frontier first.

// BFS: shortest in hops, ignores weights
// Dijkstra: shortest in total weight
// Example: A→B costs 1, A→C costs 10, C→B costs 1
// BFS says A→B is 1 hop (shortest)
// Dijkstra says A→B costs 1 (also shortest by weight)
// But if A→B costs 100, A→C→B costs 11
// BFS still says A→B is 1 hop
// Dijkstra correctly finds A→C→B costs 11

What are edge cases?

• Source equals destination: BFS terminates immediately with distance 0.
• Disconnected graph: BFS from one component cannot reach nodes in another; return not-found.
• Single node with no edges: BFS visits only the source.
• Self-loops: the visited set prevents processing a node twice even with a self-loop.

What are common mistakes?

The first mistake is marking a node visited at dequeue time instead of enqueue time. This causes the same node to be enqueued multiple times from different neighbors, wasting time and potentially causing incorrect results.

// WRONG: mark at dequeue time
String current = queue.poll();
visited.add(current);  // too late, may already be enqueued multiple times

// CORRECT: mark at enqueue time
if (visited.add(neighbor)) {
    queue.offer(neighbor);
}

What about level-order processing?

To process nodes level by level (useful for tree level-order traversal or finding the distance to each node), record the queue size at the start of each level and process exactly that many nodes before moving to the next level.

int level = 0;
while (!queue.isEmpty()) {
    int levelSize = queue.size();
    for (int i = 0; i < levelSize; i++) {
        String node = queue.poll();
        // Process node at this level
    }
    level++;
}

What should a senior engineer know?

BFS memory can be heavy because the queue may hold an entire level at once. For a balanced binary tree, the widest level has about n/2 nodes. For very wide graphs, this memory cost is significant. Bidirectional BFS from both source and target can dramatically reduce the search space for shortest-path queries.

At the National Bank of India, Rajesh used BFS in fraud analysis. Starting from a suspect account, the fraud team wanted every account reachable through chains of transfers and how many hops away each one is. Since each transfer is a single unweighted hop, BFS gave both the reachable set and the minimum-hop distance in one pass.