Breadth-First Search (BFS)

CORE INTUITION

The Queue: First In, Closest First

🔵

Why a Queue?

BFS explores nodes in order of their distance from the start. A queue (FIFO) naturally enforces this: we process nodes in the order they were discovered, ensuring we finish one level before moving to the next.

When to use: Shortest path in unweighted graphs, level-order tree traversal, topological ordering, finding connected components.

VISUALIZER

Interactive Grid Pathfinder (BFS)

Click empty cells to toggle walls (stone blocks). Watch the queue grow and shrink as BFS searches radially to find the target.
Visited cells are shaded by BFS depth — darker green means closer to the start, so you can see the "rings" expand level by level.

🧱

Simulation Status

Click Play or step forward to start.

FIFO QUEUE (Front → Back)Size: 1

Delay:400ms

THEORY

Queue Node Lifecycle & The Visited Trap

In BFS graph traversal, nodes pass through a strict lifecycle of states. To handle this properly, standard implementations use a visited tracker (like a set or boolean array).

The Three States

White (Unvisited): Undiscovered node.
Gray (Queued): Added to queue, waiting to be processed.
Black (Processed): Popped, neighbors checked.

The Visited Trap

CRITICAL RULE: Always mark a node as visited immediately when pushing it to the queue.

If you wait to mark it visited until it is popped, multiple other nodes will keep pushing the same unvisited neighbor onto the queue, causing exponential redundant operations and heap memory overflows!

BLUEPRINTS

Essential BFS Strategies

1. Standard BFS Template

How it Works

Pushes start node onto a FIFO queue.
Extracts front node, checks neighbors.
Uses a visited set to avoid double-processing cycles.
Ensures O(V + E) time and space.

bfsTemplate.js

function bfs(startNode) {

const queue = [startNode];

const visited = new Set([startNode]);

while (queue.length > 0) {

const node = queue.shift();

// Process node here

for (const neighbor of node.neighbors) {

if (!visited.has(neighbor)) {

visited.add(neighbor); // Mark visited IMMEDIATELY when pushed

queue.push(neighbor);

}

2. Binary Tree Level Order

How it Works

Extracts level size before running child iteration.
Uses an inner loop to flush one complete level in a single pass.
Pushes child nodes (left and right) for subsequent layer processing.
Gathers values into horizontal arrays row-by-row.

levelOrder.js

function levelOrder(root) {

if (!root) return [];

const result = [];

const queue = [root];

while (queue.length > 0) {

const levelSize = queue.length;

const currentLevel = [];

for (let i = 0; i < levelSize; i++) {

const node = queue.shift();

currentLevel.push(node.val);

if (node.left) queue.push(node.left);

if (node.right) queue.push(node.right);

}

result.push(currentLevel);

}

return result;

}

3. Shortest Path on Graph

How it Works

Enqueues path coordinates or step sizes alongside node ID.
Since BFS explores in absolute radial levels, the first match is guaranteed to be shortest.
Guards visited nodes to avoid looping back.
Ideal for unweighted graphs (grids, mazes).

shortestPath.js

function shortestPath(graph, start, target) {

const queue = [start];

const visited = new Set([start]);

const parentMap = new Map();

while (queue.length > 0) {

const node = queue.shift();

if (node === target) {

// Reconstruct path

const path = [];

let curr = target;

while (curr !== start) {

path.push(curr);

curr = parentMap.get(curr);

}

path.push(start);

return path.reverse();

}

for (const neighbor of graph.get(node) || []) {

if (!visited.has(neighbor)) {

visited.add(neighbor);

parentMap.set(neighbor, node);

queue.push(neighbor);

}

return []; // Unreachable

}

BFS vs DFS

When to Use Which

BFS (Queue)

Shortest path (unweighted)
Level-order traversal
Topological sort (Kahn's)
Closest target in a grid

DFS (Stack)

Path existence (any path)
Topological sort (post-order)
Cycle detection (directed)
Backtracking / combination searches

Memory Footprint: Width vs Depth

Space complexity of search algorithms depends on the shape of the search tree/graph:
• BFS Space Complexity: Bounded by the graph's maximum width (O(W)). For a perfect binary tree, the leaf level contains N/2 nodes, causing a worst-case space footprint of O(N) to hold the active level in the queue.
• DFS Space Complexity: Bounded by the graph's maximum depth (O(H)) because the call stack only retains active ancestors along the current search branch. For a balanced binary tree, the depth is O(log N), which is highly memory efficient!

APPLICATIONS

Real-world BFS Systems

1. Web Crawling & Indexing

Problem: Traverse links to discover and index websites.
Core Logic: Search engine crawlers typically use BFS. Starting from popular root URLs, links are parsed and enqueued. Traversing in level-order ensures that sites closer to the root (more popular/linked sites) are indexed first, preventing the crawler from getting stuck in deep, obscure link directories.

2. Peer-to-Peer (P2P) Networks

Problem: Broadcast messages or search files across network peers.
Core Logic: In decentralized networks, search messages are flooded to adjacent peers. BFS ensures the search spreads radially outwards, finding matching files in the closest peers first to minimize network latency.

3. Social Network Connections (Degrees of Separation)

Problem: Identify 1st, 2nd, and 3rd degree connections on platforms like LinkedIn.
Core Logic: We run BFS from the target user. Level 1 retrieves direct friends, Level 2 retrieves friends of friends (2nd degree), and Level 3 retrieves 3rd degree connections.

PITFALLS

Common Mistakes

Marking Visited on Pop

Waiting to mark a node visited until it's popped (instead of the moment it's pushed) lets several other queued nodes discover and re-push the same neighbor before it's processed — the queue bloats with duplicates and BFS gets slow.

Array as Queue

array.shift() (JS) or list.pop(0) (Python) is O(N) because every remaining element shifts down an index. On large graphs this silently degrades BFS to O(N²). Use a real queue — collections.deque in Python, an index pointer or linked list in JS.

Forgetting Visited Entirely

Skip the visited set and BFS on any graph with a cycle re-queues the same nodes forever, never terminating. Always track visited — and mark it on push, not on pop.

PRACTICE

Ready to Practice?

Shortest Path in Binary MatrixMedium

Rotting OrangesMedium

Word LadderHard

"BFS = queue. Distance order. Closest first."