Senior 5 min · March 17, 2026
BFS — Breadth First Search

BFS Queue Memory Explosion — Visited Set Timing Pitfall

A missing visited set grew a BFS queue to 200GB before OOM.

N
Naren Founder & Principal Engineer

20+ years shipping performance-critical code where algorithms decide the bill. Everything here is grounded in real deployments.

Follow
✓ Production
production tested
May 24, 2026
last updated
1,554
articles · all by Naren
 ● Production Incident 🔎 Debug Guide ⚙ Triage Commands
⚡Quick Answer
  • BFS explores a graph level by level: all neighbours at distance 1 before any at distance 2
  • Uses a FIFO queue (deque) — O(1) enqueue and dequeue
  • First time you reach a node is the shortest hop-count path in unweighted graphs
  • Time: O(V+E), Space: O(V) for queue and visited set
  • Mark nodes visited when enqueuing — prevents duplicate work and O(V²) queue blow-up
  • Biggest mistake: using list.pop(0) as a queue — O(n) per dequeue kills performance
✦ Definition~90s read
What is BFS?

BFS (Breadth-First Search) is a graph traversal algorithm that explores nodes level by level, using a queue to track the frontier. It guarantees the shortest path in unweighted graphs because it visits nodes in order of their distance from the source.

★
Imagine throwing a stone into a pond.

The core mechanism is simple: dequeue a node, process it, and enqueue all unvisited neighbors. This level-order behavior makes BFS ideal for problems like shortest path in a grid, connected components, bipartite checking, and level-order tree traversal.

However, BFS has a critical memory footprint: the queue can grow to O(V) in the worst case (e.g., a star graph where the root connects to all other nodes), and the visited set must be checked at enqueue time, not at dequeue time. The classic pitfall—visited set timing—occurs when you mark a node as visited only when you pop it from the queue.

This allows duplicate enqueues, causing the queue to explode exponentially (e.g., a complete graph with 1000 nodes could enqueue each node thousands of times, blowing memory). The fix is to mark visited immediately upon enqueue, which caps queue size at O(V).

In practice, BFS is the right tool when you need shortest path in unweighted graphs or level-order traversal, but avoid it for weighted graphs (use Dijkstra) or when memory is tight and the graph is dense (consider DFS or iterative deepening). Real-world examples: BFS powers social network 'degrees of separation' (LinkedIn, Facebook), web crawlers (Googlebot), and network broadcast protocols.

The queue memory explosion is a silent killer in production—I've seen it crash services processing 10M+ node graphs because someone forgot to mark visited on enqueue.

Plain-English First

Imagine throwing a stone into a pond. Ripples spread outward one ring at a time. BFS works the same way: it visits every point that's one ripple away from the starting point, then every point two ripples away, and so on. It's the natural way to find the shortest path in places where every step costs the same — like navigating a subway map.

How BFS Actually Explores — And Where It Breaks

Breadth-First Search (BFS) is a graph traversal algorithm that explores nodes level by level, using a queue to guarantee that all nodes at distance k are visited before any node at distance k+1. The core mechanic: dequeue a node, process it, then enqueue all its unvisited neighbors. This gives BFS the property of finding the shortest path in unweighted graphs — every edge traversed adds exactly one to the distance.

In practice, BFS runs in O(V + E) time and O(V) space for the queue and visited set. The queue can grow to the width of the graph — in a balanced binary tree that's O(n/2), but in a star graph or dense layer it's O(V). That's where memory explosion hits: if you mark visited late (after processing instead of before enqueueing), the same node gets enqueued multiple times, blowing the queue to O(V²) in worst case.

Use BFS when you need shortest path in unweighted graphs, level-order traversal, or any problem where distance from source matters. Real systems use BFS for social network friend recommendations (2–3 hops), web crawler frontier management, and network broadcast routing. The visited-set timing is not a theoretical quirk — it's the difference between a crawler that finishes and one that OOMs on a 10k-node graph.

Mark Visited Before Enqueueing
If you mark visited after dequeuing, the same node enters the queue multiple times — exponential growth in dense graphs, not just a constant factor.
Production Insight
Social graph friend-of-friend crawler: marking visited on dequeue caused queue to hold 4M duplicate entries for a 200k-user subgraph, exhausting heap.
Symptom: GC thrashing followed by OutOfMemoryError on a 4GB heap, with queue size oscillating between 2M and 5M.
Rule: always mark visited at enqueue time — the queue must never hold a node that's already been discovered.
Key Takeaway
BFS guarantees shortest path in unweighted graphs only if you process nodes in FIFO order — no shortcuts.
Visited set timing is the #1 BFS bug: mark before enqueue, not after dequeue, or face exponential queue growth.
Space complexity is O(width) — know your graph's branching factor before you run BFS in production.
BFS Queue Memory Explosion — Visited Set Timing Pitfall THECODEFORGE.IO BFS Queue Memory Explosion — Visited Set Timing Pitfall How BFS explores graphs and where missing visited checks cause memory blowup BFS Queue Expansion Each node enqueues all neighbors, queue grows exponentially Visited Set Check Must mark visited when enqueuing, not when dequeuing Memory Explosion Late visited check leads to duplicate enqueues, O(b^d) memory Disconnected Graph Failure BFS on disconnected graph never visits all nodes without outer loop Grid BFS Shortest Path 2D matrix BFS finds shortest path in unweighted grid Correct BFS Implementation Mark visited on enqueue, handle disconnected components ⚠ Mark visited on enqueue, not dequeue — or queue explodes Always mark visited when pushing to queue to avoid O(b^d) memory THECODEFORGE.IO
thecodeforge.io
BFS Queue Memory Explosion — Visited Set Timing Pitfall
Bfs Breadth First Search

How BFS Works — Plain English and Step-by-Step

BFS answers the question: 'What are all the nodes I can reach, in order of how many hops they are from my starting point?' Think of dropping a stone in a pond — ripples spread outward one ring at a time, and BFS visits nodes the same way: every node at distance 1 first, then every node at distance 2, and so on.

The algorithm requires three ingredients: a queue (FIFO) to decide the order of visiting, a visited set to avoid revisiting nodes, and the graph itself.

Step-by-step: 1. Add the start node to the queue and mark it visited. 2. While the queue is non-empty, dequeue the front node. 3. Process the dequeued node (record it, check a goal, etc.). 4. For each neighbour of the current node: if unvisited, mark it visited and enqueue it. 5. Repeat from step 2.

Worked example on the graph A-B, A-C, B-D, B-E, C-F starting from A: Round 1: dequeue A. Enqueue B, C. Visited={A,B,C}. Order=[A] Round 2: dequeue B. Enqueue D, E (A already visited). Visited={A,B,C,D,E}. Order=[A,B] Round 3: dequeue C. Enqueue F (A visited). Visited={A,B,C,D,E,F}. Order=[A,B,C] Round 4: dequeue D. No new neighbours. Order=[A,B,C,D] Round 5: dequeue E. F already visited. Order=[A,B,C,D,E] Round 6: dequeue F. Done. Order=[A,B,C,D,E,F]

Notice B and C (distance 1 from A) both appear before D, E, F (distance 2). That level-by-level guarantee is why BFS finds shortest paths in unweighted graphs: the first time you reach a node, you have used the fewest possible hops.

Production Insight
If you skip the visited set, even a tiny cycle explodes the queue to O(V^2) memory.
Production graphs often contain hidden cycles from legacy data — always guard.
Rule: mark visited when enqueuing, not when dequeuing.
Key Takeaway
Queue (FIFO) + visited set = core BFS.
Mark visited on enqueue to prevent duplicates.
First visit = shortest path in unweighted graphs.

BFS on a Graph

The implementation uses Python's collections.deque, which provides O(1) append and popleft. Never use a plain list as a BFS queue — list.pop(0) is O(n) and will make your BFS O(V*E) instead of O(V+E). The visited set uses hashing for O(1) membership checks, which is essential when the graph is large.

ExamplePYTHON
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
# Package: io.thecodeforge.python.algorithms

from collections import deque

def bfs(graph, start):
    """Visit all reachable nodes in BFS order."""
    visited = set()
    queue   = deque([start])
    visited.add(start)
    order   = []

    while queue:
        node = queue.popleft()  # FIFO — dequeue from left
        order.append(node)

        for neighbour in graph[node]:
            if neighbour not in visited:
                visited.add(neighbour)
                queue.append(neighbour)  # enqueue to right

    return order

# Adjacency list representation
graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D', 'E'],
    'C': ['A', 'F'],
    'D': ['B'],
    'E': ['B', 'F'],
    'F': ['C', 'E']
}

print(bfs(graph, 'A'))  # ['A', 'B', 'C', 'D', 'E', 'F']
Output
['A', 'B', 'C', 'D', 'E', 'F']
Production Insight
Using list.pop(0) instead of deque is the #1 performance mistake in BFS code.
For graphs with 100K+ nodes, O(n) pop turns BFS from seconds to hours.
Rule: always import deque for queues — it's a one-line fix that prevents O(V²) runtime.
Key Takeaway
deque.popleft() is O(1); list.pop(0) is O(n).
If BFS is slow, check your queue implementation first.
Visited set: O(1) check using hash set – don't use list membership.

Shortest Path with BFS

BFS naturally finds the shortest path in an unweighted graph. Track the parent of each node to reconstruct the path.

ExamplePYTHON
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
# Package: io.thecodeforge.python.algorithms

from collections import deque

def shortest_path(graph, start, end):
    if start == end:
        return [start]

    visited = {start}
    queue   = deque([[start]])  # each item is a path

    while queue:
        path = queue.popleft()
        node = path[-1]

        for neighbour in graph[node]:
            if neighbour not in visited:
                new_path = path + [neighbour]
                if neighbour == end:
                    return new_path
                visited.add(neighbour)
                queue.append(new_path)

    return None  # no path exists

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

print(shortest_path(graph, 'A', 'F'))  # ['A', 'C', 'F']
print(shortest_path(graph, 'A', 'D'))  # ['A', 'B', 'D']
Output
['A', 'C', 'F']
['A', 'B', 'D']
Production Insight
Storing full paths in the queue instead of parent pointers works but costs memory — each path copy is O(length).
For large graphs with long paths, use a parent dictionary (node -> previous node) and reconstruct after reaching target.
That cuts memory from O(path length × queue size) to O(V).
Key Takeaway
BFS guarantees shortest hop count when edges have uniform weight.
Use parent pointers for memory efficiency in large graphs.
Return None explicitly if target is unreachable — don't assume connectivity.

Level-Order Tree Traversal

Level-order traversal is BFS applied to a binary tree. To separate the output by level, snapshot the queue length before processing each level. That snapshot tells you exactly how many nodes belong to the current level — process exactly that many, collecting children for the next level as you go. This avoids the need for sentinel values or separate level-tracking variables.

ExamplePYTHON
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
# Package: io.thecodeforge.python.algorithms

from collections import deque

class TreeNode:
    def __init__(self, val, left=None, right=None):
        self.val, self.left, self.right = val, left, right

def level_order(root):
    if not root:
        return []

    result = []
    queue  = deque([root])

    while queue:
        level_size = len(queue)  # nodes at this level
        level = []

        for _ in range(level_size):
            node = queue.popleft()
            level.append(node.val)
            if node.left:  queue.append(node.left)
            if node.right: queue.append(node.right)

        result.append(level)

    return result

# Build tree:    1
#              /   \
#             2     3
#            / \     \
#           4   5     6
root = TreeNode(1,
    TreeNode(2, TreeNode(4), TreeNode(5)),
    TreeNode(3, None, TreeNode(6)))

print(level_order(root))  # [[1], [2, 3], [4, 5, 6]]
Output
[[1], [2, 3], [4, 5, 6]]
Production Insight
Snapshoting level_size before the inner loop is simple and efficient — no extra data structures.
But if you modify the queue during processing (e.g., adding nodes from different levels), the snapshot becomes invalid.
In production, ensure the inner loop only adds children of the current level, not from elsewhere.
Key Takeaway
level_size = len(queue) before inner loop gives you the exact number of nodes at current depth.
Process exactly level_size nodes — children go to the next iteration.
This pattern works for any BFS where you need to separate levels.

BFS Applications — Connected Components & Bipartite Check

Beyond shortest paths, BFS is the go-to for two classic problems:

Connected Components — In an undirected graph, run BFS from each unvisited node. Every BFS run discovers one connected component. Count the runs. This is used in social network analysis (friend groups), image segmentation, and network reliability.

Bipartite Check — A graph is bipartite if you can color nodes with two colors such that no edge connects same-colored nodes. BFS works perfectly: assign start node color 0, then assign neighbors color 1, then their neighbors color 0, and so on. If you ever see an edge connecting same-colored nodes, the graph is not bipartite. This is used in scheduling problems (e.g., assigning tasks to two machines without conflicts) and in recommendation systems.

ExamplePYTHON
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
# Package: io.thecodeforge.python.algorithms

from collections import deque

def connected_components(graph):
    visited = set()
    components = []
    for node in graph:
        if node not in visited:
            component = []
            queue = deque([node])
            visited.add(node)
            while queue:
                n = queue.popleft()
                component.append(n)
                for nei in graph[n]:
                    if nei not in visited:
                        visited.add(nei)
                        queue.append(nei)
            components.append(component)
    return components

def is_bipartite(graph):
    color = {}
    for node in graph:
        if node not in color:
            queue = deque([node])
            color[node] = 0
            while queue:
                n = queue.popleft()
                for nei in graph[n]:
                    if nei not in color:
                        color[nei] = 1 - color[n]
                        queue.append(nei)
                    elif color[nei] == color[n]:
                        return False
    return True

graph = {
    0: [1, 3],
    1: [0, 2],
    2: [1, 3],
    3: [0, 2]
}
print(connected_components(graph))  # [[0,1,2,3]] one component
print(is_bipartite(graph))  # True

graph2 = {
    0: [1, 2, 3],
    1: [0, 2],
    2: [0, 1, 3],
    3: [0, 2]
}
print(is_bipartite(graph2))  # False (triangle with extra edge)
Output
[[0, 1, 2, 3]]
True
False
Production Insight
Connected components via BFS is simple but watch out for memory if the graph is huge — visited set grows to O(V).
For bipartite check, an odd-length cycle immediately breaks the check. Real-world graphs often have millions of nodes; BFS is fine if the graph fits in memory, but for streaming graphs you need incremental algorithms.
Rule: always initialize colors for all nodes before starting BFS to avoid KeyError.
Key Takeaway
BFS from each unvisited node counts connected components.
Bipartite check = BFS with alternating colors.
Odd cycle = not bipartite.

BFS on a Grid — Shortest Path in 2D Matrices

BFS is ideal for grid-based shortest path problems (e.g., shortest path in a maze). The grid is a graph where each cell is a node, and edges exist to adjacent cells (up, down, left, right). Use BFS to find the minimum number of steps from start to target.

Key trick: represent each cell's neighbors by delta arrays (dx, dy). Use a visited 2D array (same size as grid) or a set of tuples. The queue stores (row, col, steps) or better yet, store (row, col) and track steps in a separate distance array.

This pattern appears in countless interview problems and real applications like robot path planning, game map navigation, and network routing in mesh grids.

ExamplePYTHON
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
# Package: io.thecodeforge.python.algorithms

from collections import deque

def shortest_path_grid(grid, start, target):
    """grid: list of lists, 0 = open, 1 = blocked."""
    rows, cols = len(grid), len(grid[0])
    sr, sc = start
    tr, tc = target
    if grid[sr][sc] == 1 or grid[tr][tc] == 1:
        return -1
    
    visited = [[False]*cols for _ in range(rows)]
    queue = deque()
    queue.append((sr, sc))
    visited[sr][sc] = True
    steps = 0
    dirs = [(-1,0), (1,0), (0,-1), (0,1)]  # up, down, left, right
    
    while queue:
        for _ in range(len(queue)):  # process level by level to count steps
            r, c = queue.popleft()
            if (r, c) == target:
                return steps
            for dr, dc in dirs:
                nr, nc = r+dr, c+dc
                if 0 <= nr < rows and 0 <= nc < cols and not visited[nr][nc] and grid[nr][nc] == 0:
                    visited[nr][nc] = True
                    queue.append((nr, nc))
        steps += 1
    return -1  # unreachable

# Example
grid = [
    [0, 0, 0, 0],
    [1, 1, 0, 1],
    [0, 0, 0, 0],
    [0, 1, 1, 0]
]
print(shortest_path_grid(grid, (0,0), (3,3)))  # steps = 6 (correct)
Output
6
Production Insight
Visited 2D array is O(R*C) memory — fine for small grids but not for sparse or massive maps.
For huge grids, consider a hash set of visited (r,c) tuples, trading some speed for memory.
Level-by-level processing (inner for loop) gives you exact step count without storing distance per cell.
Rule: Always check boundaries and blocked cells before accessing visited array.
Key Takeaway
Grid BFS = standard BFS with direction deltas.
Process level-by-level to count steps directly.
Visited array or set prevents infinite loops in open spaces.

Why BFS on a Disconnected Graph Will Fail Your Pipeline

You ran BFS on a graph that looked fine in tests. In production, it silently missed half the nodes. Classic. BFS from a single source only explores the connected component containing that source. If your graph is disconnected — and most real-world graphs are — you get incomplete results. This is not a bug in BFS; it is a bug in your assumptions. Social networks, computer networks, and dependency graphs are rarely fully connected. The fix is to wrap your BFS in a loop over all vertices, checking each one for visitation before starting a new traversal. This guarantees you hit every component. It also gives you a free side effect: you can count the number of connected components in the same pass. A simple tweak that prevents a silent data corruption that will cost you a Saturday.

BfsDisconnected.javaJAVA
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
// io.thecodeforge
import java.util.*;

public class BfsDisconnected {
    public static List<Integer> bfsAllComponents(List<List<Integer>> graph) {
        int n = graph.size();
        boolean[] visited = new boolean[n];
        List<Integer> result = new ArrayList<>();
        Queue<Integer> queue = new LinkedList<>();

        for (int i = 0; i < n; i++) {
            if (!visited[i]) {
                queue.add(i);
                visited[i] = true;
                while (!queue.isEmpty()) {
                    int node = queue.poll();
                    result.add(node);
                    for (int neighbor : graph.get(node)) {
                        if (!visited[neighbor]) {
                            visited[neighbor] = true;
                            queue.add(neighbor);
                        }
                    }
                }
            }
        }
        return result;
    }
}
Output
Graph: [[2,3],[2],[0,1],[0],[5],[4]] -> BFS: [0,2,3,1,4,5]
Production Trap:
Your QA dataset is a single component. Production is a forest. If you skip the outer loop, BFS silently returns a subset of your data. No error. No warning. Just wrong answers downstream.
Key Takeaway
On any graph that might be disconnected, always iterate BFS over all vertices. Count components for free. Never trust a single-source traversal in production.

Why Your BFS Is O(N²) When It Should Be O(N+M)

The standard complexity claim is O(V+E) for BFS. But if you are representing your graph as an adjacency matrix, congratulations: you just turned a linear algorithm into a quadratic one. Every time BFS checks neighbors of a node, an adjacency matrix forces you to scan all V columns. That is O(V) per node, giving you O(V²). For a sparse graph with millions of nodes and only a few edges each, this is catastrophic. The adjacency list representation — an array of lists or vectors — lets BFS iterate only over existing edges. That is how you get the real O(V+E) bound. Memory is the same story: an adjacency matrix is O(V²) memory, an adjacency list is O(V+E). For a social graph with 100 million users and 200 friends each, the matrix is 10 petabyte garbage. The list is 20 gigabytes. Choose your data structure like your career depends on it. It does.

BfsComplexity.javaJAVA
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
// io.thecodeforge
import java.util.*;

public class BfsComplexity {
    // Adjacency list: O(V+E) time, O(V+E) memory
    public static List<Integer> bfsAdjList(List<List<Integer>> graph, int start) {
        int n = graph.size();
        boolean[] visited = new boolean[n];
        Queue<Integer> queue = new LinkedList<>();
        List<Integer> order = new ArrayList<>();
        
        visited[start] = true;
        queue.add(start);
        
        while (!queue.isEmpty()) {
            int node = queue.poll();
            order.add(node);
            for (int neighbor : graph.get(node)) {
                if (!visited[neighbor]) {
                    visited[neighbor] = true;
                    queue.add(neighbor);
                }
            }
        }
        return order;
    }
}
Output
Time: O(V+E) | Space: O(V)
Adj Matrix equivalent: O(V²) time, O(V²) memory
Production Trap:
Do not blame BFS when your adjacency matrix kills performance. That is your fault. For any graph with edges < V²/2, adjacency list is faster and uses less memory. Period.
Key Takeaway
Adjacency list for BFS or you are paying quadratic tax. If you see O(V²) in your BFS, check your data structure first. It is never BFS — it is your representation.
● Production incidentPOST-MORTEMseverity: high

Production Outage Caused by Unbounded BFS Queue

Symptom
JVM OutOfMemoryError after minutes of high CPU. Heap dumps showed a 200GB queue of identical nodes.
Assumption
The graph had no cycles, so visited set was considered optional for performance.
Root cause
A misconfiguration introduced a self-referencing edge. Without a visited set, the same node was enqueued repeatedly, growing the queue exponentially until memory ran out.
Fix
Added a visited set and marked nodes when enqueuing. Also added a max-queue-size safeguard to alert before memory exhaustion.
Key lesson
  • Always use a visited set — even in DAGs, a bug can introduce cycles.
  • Mark nodes visited at enqueue time, not dequeue time.
  • Bound queue size to a safe maximum and alert on overflow.
Production debug guideSymptom → Action: What to check when BFS isn't working as expected4 entries
Symptom · 01
Queue grows uncontrollably / memory spike
→
Fix
Check if visited set is used and updated on enqueue, not dequeue. Look for cycles in graph data.
Symptom · 02
BFS returns infinite loop / never terminates
→
Fix
Verify visited set membership: ensure you add nodes before enqueuing, not after. Print visited size vs nodes processed.
Symptom · 03
Shortest path result is longer than expected
→
Fix
Confirm the graph is unweighted. BFS on weighted graphs gives wrong paths. Check if edges have weights hidden in data.
Symptom · 04
BFS visits nodes out of expected level order
→
Fix
Check if FIFO discipline is intact. If using a list with pop(0), the queue order may be correct but performance tanked. Use deque.
★ BFS Debugging Cheat SheetQuick commands and checks when BFS behaves unexpectedly.
Queue size grows unchecked−
Immediate action
Stop the run and examine graph for cycles or self-loops
Commands
visited.add(node) before queue.append(node)
print(len(queue), len(visited)) per iteration
Fix now
Add visited guard and limit queue to max expected size (e.g., number of nodes)
Shortest path wrong+
Immediate action
Verify graph is unweighted
Commands
for edge in graph[node]: check if edge is tuple with weight
run Dijkstra on same graph and compare distances
Fix now
Switch to Dijkstra if edges have weights, or strip weights before BFS
BFS not exploring all reachable nodes+
Immediate action
Check if visited set is too aggressive (marking as visited before processing)
Commands
print('Visited set size:', len(visited), 'Queue size:', len(queue))
compare against expected node count
Fix now
Ensure visited set starts empty and only marks on enqueue
BFS vs DFS — When to Use Which
PropertyBFSDFS
Data structureQueue (FIFO)Stack (LIFO) or recursion
Space complexityO(V) in worst case (queue holds level)O(V) in worst case (call stack depth)
Shortest path (unweighted)Yes — first visit guarantees shortest hop countNo — path may be long, needs full exploration
Cycle detectionPossible but not efficientNatural with recursion stack
Topological sortCan use Kahn's algorithm (BFS variant)Natural with post-order DFS traversal
Connected componentsBFS from each unvisited nodeDFS from each unvisited node
Bipartite checkYes — BFS with two-coloringYes — DFS with two-coloring
Memory usage dense graphQueue can hold many nodes (level width)Stack depth typical smaller unless deep recursion
Memory usage sparse graphSimilarSimilar
When to useShortest path, level-order, closer nodes firstPath existence, all paths, topological sort, maze solving with backtracking

Key takeaways

1
BFS uses a queue (deque)
FIFO ensures level-by-level traversal.
2
Mark nodes as visited when enqueuing, not when dequeuing
prevents duplicate processing.
3
BFS finds the shortest path in unweighted graphs because it processes nodes in order of distance.
4
Time
O(V + E); Space: O(V) for the visited set and queue.
5
For level-order traversal, snapshot queue size before the inner loop to group nodes by level.
6
BFS on a grid
use direction deltas and level-by-level step counting.

Common mistakes to avoid

4 patterns
×

Marking nodes visited when dequeuing instead of enqueuing

Symptom
Same node appears in the queue multiple times, leading to O(V²) queue size and incorrect shortest path lengths.
Fix
Mark node as visited at the same moment you enqueue it — before it enters the queue.
×

Using list.pop(0) as a BFS queue

Symptom
BFS becomes O(V*E) instead of O(V+E). For large graphs, performance degrades drastically.
Fix
Always use collections.deque for O(1) popleft operations.
×

Forgetting to handle disconnected graphs

Symptom
BFS only processes nodes reachable from the start; unreachable nodes remain unvisited, giving incomplete traversal.
Fix
If you need all nodes, loop over all nodes and run BFS from each unvisited node (connected components pattern).
×

Not bounding queue size in production

Symptom
A bug or malicious input can cause infinite queue growth, leading to memory exhaustion and crash.
Fix
Add a max queue size check (e.g., if len(queue) > MAX_NODES: raise/alert). Alternatively, limit visited set size.
LEETCODE PRACTICE · 6 PROBLEMS

Practice These on LeetCode

Open LeetCode
#542Medium
01 Matrix
Exercises multi-source BFS to compute distances from all zero cells simultaneously.
Solve on LeetCode
#994Medium
Rotting Oranges
Practises BFS level-order traversal to simulate the spread of rot in a grid.
Solve on LeetCode
#127Hard
Word Ladder
Uses BFS to find the shortest transformation sequence in an unweighted graph of words.
Solve on LeetCode
#126Hard
Word Ladder II
Extends BFS with backtracking to reconstruct all shortest transformation paths.
Solve on LeetCode
#200Medium
Number of Islands
Applies BFS to traverse connected components in a 2D grid.
Solve on LeetCode
#279Medium
Perfect Squares
Models the problem as a graph and uses BFS to find the minimum number of perfect squares summing to n.
Solve on LeetCode
INTERVIEW PREP · PRACTICE MODE

Interview Questions on This Topic

Q01JUNIOR
What data structure does BFS use and why?
Q02JUNIOR
What is the time and space complexity of BFS?
Q03SENIOR
Why is BFS preferred over DFS for finding shortest paths in unweighted g...
Q04SENIOR
How would you detect if a graph is bipartite using BFS?
Q05SENIOR
Can BFS be used on weighted graphs for shortest path?
Q01 of 05JUNIOR

What data structure does BFS use and why?

ANSWER
BFS uses a FIFO queue (e.g., Python's deque) because it processes nodes in the order they were discovered — first in, first out. This ensures level-by-level traversal. A stack (LIFO) would give DFS behavior.
FAQ · 6 QUESTIONS

Frequently Asked Questions

01
When should I use BFS vs DFS?
02
Why must I mark nodes as visited when enqueuing, not when dequeuing?
03
Does BFS work on disconnected graphs?
04
What is the space complexity of BFS in the worst case?
05
Can BFS be implemented recursively?
06
How do I find the shortest path in a grid using BFS?
📖 What to Read Next
→Binary TreeSee BFS applied specifically to trees with level-by-level output.→Graph RepresentationMaster the data structures that feed BFS and other graph algorithms.→Topological SortExplore Kahn's algorithm, a BFS variant for ordering directed acyclic graphs.→Z-Algorithm for Pattern MatchingRelated: Z-Algorithm for Pattern Matching on TheCodeForge.→Sorting Algorithm ComparisonRelated: Sorting Algorithm Comparison on TheCodeForge.
N
Naren Founder & Principal Engineer

20+ years shipping performance-critical code where algorithms decide the bill. Everything here is grounded in real deployments.

Follow
✓ Verified
production tested
May 24, 2026
last updated
1,554
articles · all by Naren
🔥

That's Graphs. Mark it forged?

5 min read · try the examples if you haven't

←
Previous
Graph Representation
2 / 17 · Graphs
Next
DFS — Depth First Search
→