Breadth-First Search (BFS) Complete Guide

Algorithm • medium

BFS explores a graph layer by layer using a **queue**: visit a node, enqueue its unvisited neighbors, repeat until the queue is empty.

On an unweighted graph, the first time BFS reaches a node is along a shortest path. This is the single most important property of BFS.

It runs in O(V + E) time and O(V) space touching every vertex and every edge at most a constant number of times.

Typical Complexity Baseline

Metric	Value
Time	`O(V + E)`
Space	`O(V)`

See It

Concept Diagram

A small animated SVG that illustrates the core idea the moving parts you need to keep in your head when you read the rest of the guide.

BFS expand by layer

All nodes at distance d are visited before any at distance d + 1.

Step 1/18Init. Mark S visited, queue = [S].

Speed

Watch First

Video Explainer

A quick visual walkthrough before the detailed sections pick the format that helps you learn fastest.

Breadth-first search in 4 minutes

Channel: Michael Sambol

Watch on YouTube →

Mechanics

Core Concepts

The building blocks and terminology you need before everything else clicks. Skim or deep-read.

Queue (FIFO)

What it is Holds the frontier nodes discovered but not yet expanded. Use a deque for O(1) popleft.

Why it matters Queue (FIFO) is a required building block for understanding how Breadth-First Search (BFS) stays correct and performant on large inputs.

Visited set

What it is Records which nodes have been enqueued so each is processed exactly once. Without it, cycles cause infinite loops.

Why it matters Visited set is a required building block for understanding how Breadth-First Search (BFS) stays correct and performant on large inputs.

Distance / parent map

What it is Optional bookkeeping: distance from source, parent pointers for path reconstruction.

Why it matters Distance / parent map is a required building block for understanding how Breadth-First Search (BFS) stays correct and performant on large inputs.

Level boundary

What it is Implicit or explicit marker between BFS layers useful when you need 'all nodes at depth k'.

Why it matters Level boundary is a required building block for understanding how Breadth-First Search (BFS) stays correct and performant on large inputs.

Frontier

What it is The set of nodes currently in the queue the wavefront of exploration.

Why it matters The set of nodes currently in the queue the wavefront of exploration. In Breadth-First Search (BFS), this definition helps you reason about correctness and complexity when inputs scale.

Layer (level)

What it is All nodes at the same distance from the source. BFS processes layers in order.

Why it matters All nodes at the same distance from the source. BFS processes layers in order. In Breadth-First Search (BFS), this definition helps you reason about correctness and complexity when inputs scale.

Unweighted shortest path

What it is Path with the fewest edges. BFS finds it; Dijkstra/A* are needed for weighted edges.

Why it matters Path with the fewest edges. BFS finds it; Dijkstra/A* are needed for weighted edges. In Breadth-First Search (BFS), this definition helps you reason about correctness and complexity when inputs scale.

0-1 BFS

What it is Variant using a deque push to front for weight-0 edges, back for weight-1. Solves shortest path on graphs with binary weights in O(V+E).

Why it matters Variant using a deque push to front for weight-0 edges, back for weight-1. Solves shortest path on graphs with binary weights in O(V+E). In Breadth-First Search (BFS), this definition helps you reason about correctness and complexity when inputs scale.

Multi-source BFS

What it is Seed the queue with multiple starting nodes at distance 0. Useful for 'nearest of any X' problems.

Why it matters Seed the queue with multiple starting nodes at distance 0. Useful for 'nearest of any X' problems. In Breadth-First Search (BFS), this definition helps you reason about correctness and complexity when inputs scale.

Walkthrough

Putting It All Together

Every frame of the concept diagram, laid out top-to-bottom so you can scroll through the algorithm at your own pace.

Step 1/18

Init. Mark S visited, queue = [S].

Step 2/18

Dequeue S. Examine neighbors: A, B.

Step 3/18

Enqueue A, B. Queue = [A, B].

Step 4/18

Dequeue A. Examine neighbors: S, C, D.

Step 5/18

Enqueue C, D. Queue = [B, C, D].

Step 6/18

Dequeue B. Examine neighbors: S, D.

Step 7/18

Dequeue C. Examine neighbors: A, E.

Step 8/18

Enqueue E. Queue = [D, E].

Step 9/18

Dequeue D. Examine neighbors: A, B, F.

Step 10/18

Enqueue F. Queue = [E, F].

Step 11/18

Dequeue E. Examine neighbors: C, F, G.

Step 12/18

Enqueue G. Queue = [F, G].

Step 13/18

Dequeue F. Examine neighbors: D, E, G.

Step 14/18

Dequeue G. Examine neighbors: E, F, H, I.

Step 15/18

Enqueue H, I. Queue = [H, I].

Step 16/18

Dequeue H. Examine neighbors: G.

Step 17/18

Dequeue I. Examine neighbors: G.

Step 18/18

Queue empty → BFS done. Visited 10 nodes in layer order.

Tradeoffs

How It Compares

When this technique wins, when it loses, and what to reach for instead.

vs. Depth-First Search (DFS)

Choose this when Choose BFS when you need shortest path / minimum number of steps, or layer-order processing.

Tradeoff BFS uses O(V) queue memory in the worst case (wide graphs); DFS uses O(depth) stack memory (often less).

vs. Dijkstra's Algorithm

Choose this when Choose BFS when all edge weights are equal O(V+E) is faster than Dijkstra's O((V+E) log V).

Tradeoff BFS doesn't handle weighted edges. The moment weights differ, you need Dijkstra (or 0-1 BFS for binary weights).

vs. A* search

Choose this when Choose plain BFS when you have no heuristic or the graph is small.

Tradeoff A* explores far fewer nodes when you have a good heuristic, but it's pointless without one.

In Production

Real-World Stories

Where this shows up at real companies and what the on-call engineer learned the hard way.

LinkedIn / Facebook

'Degrees of connection' (1st, 2nd, 3rd) is computed with BFS over the social graph, capped at depth 3 because the graph explodes combinatorially after that.

Takeaway BFS is the natural fit for 'how many hops away' but capping depth is essential at scale.

Web crawlers (Google, Common Crawl)

Crawlers BFS the web from seed URLs, prioritizing breadth-first to discover new domains before going deep into any one site.

Takeaway BFS gives breadth coverage; DFS would get stuck in a single domain's deep links.

Game AI (pathfinding on grids)

Simple grid-based games use BFS for enemy pathfinding when the grid is unweighted. AAA titles upgrade to A* for weighted terrain or large maps.

Takeaway BFS is the right starting point; upgrade only when profiling shows you need to.

Code

Implementation

A clean reference implementation in TypeScript, Python, and Go. Switch languages with the toggle.

Standard queue-based BFS that records the shortest distance from the source to every reachable node.

Complexity: Time O(V + E), Space O(V)

BFS with shortest-path distance tracking

Language

function shortestDistancesByBfs(params: {
  sourceNode: string
  adjacencyByNode: Map<string, string[]>
}): Map<string, number> {
  const distanceByNode = new Map<string, number>()
  const explorationQueue: string[] = [params.sourceNode]
  distanceByNode.set(params.sourceNode, 0)

  while (explorationQueue.length > 0) {
    const currentNode = explorationQueue.shift() as string
    const currentDistance = distanceByNode.get(currentNode) as number
    for (const neighborNode of params.adjacencyByNode.get(currentNode) ?? []) {
      if (distanceByNode.has(neighborNode)) continue
      distanceByNode.set(neighborNode, currentDistance + 1)
      explorationQueue.push(neighborNode)
    }
  }
  return distanceByNode
}

Watch Out

Common Problems and Failure Modes

The bugs and edge cases that bite engineers most often. Skim before you ship.

Using a list instead of a deque in Python list.pop(0) is O(n), making your BFS accidentally O(V²).
Marking nodes visited on **dequeue** instead of **enqueue** the same node gets queued multiple times, wasting work and breaking distance correctness.
Trying to use BFS on a weighted graph and getting wrong shortest distances. BFS only works when all edges have equal weight.
Forgetting to track visited on grid problems flood-fill loops forever.
Reconstructing the path by re-running BFS from each node instead, store parent pointers and walk them backwards once.

Pro Tips

Tips and Tricks

Small habits that pay off every time you reach for this pattern.

Start by writing the core invariant in one sentence before coding.
Test empty, single-item, and duplicate-heavy inputs early.
Pick the pattern first (map, pointers, recursion, heap, etc.), then implement details.
Track both time and space complexity while iterating on correctness.

Pattern Recognition

When to Use

Concrete signals that tell you this is the right pattern both at work and on LeetCode.

Real-system usage signals

Shortest path on **unweighted** graphs the canonical use case.
Level-order traversal of trees (e.g. printing a binary tree level by level).
Reachability and connectivity questions ("is B reachable from A?").
Web crawlers, social-network 'people you may know' (n-degree connections), maze solvers.
Bipartite checking, finding connected components, and flood-fill on grids.

LeetCode-specific tips (pattern-identification signals)

Identification signal: focus on verbs like optimize, order, schedule, traverse, or shortest path; these often indicate algorithm-first problems.
Identification signal: if brute force is easy to write but constraints are large, you likely need a known algorithmic pattern.
Map the prompt to pattern families first (search, traversal, greedy, DP, graph) before coding details.
For Breadth-First Search (BFS) questions, start by naming the core invariant before writing code.
Use the constraint section to set time/space target first, then pick the data structure/algorithm.
Solve one tiny example by hand and map each transition to your variables before implementing.
Run adversarial cases: empty input, duplicates, max-size input, and sorted/reverse patterns when relevant.
During interviews, explain why your approach is the right pattern for this prompt, not just why the code works.

Practice

LeetCode Progression

A curated easy-to-hard problem ladder. Each one reinforces a specific aspect of the pattern.

#	Problem	Difficulty	Typical Complexity
1	Binary Tree Level Order Traversal	Medium	`O(n)`
2	Number of Islands	Medium	`O(rows × cols)`
3	Rotting Oranges	Medium	`O(rows × cols)`, multi-source BFS
4	Shortest Path in Binary Matrix	Medium	`O(n²)`
5	01 Matrix	Medium	`O(rows × cols)`, multi-source BFS
6	Open the Lock	Medium	`O(10⁴ × 4)`
7	Word Ladder	Hard	`O(n × wordLength²)`
8	Bus Routes	Hard	`O(n × m)`