Breadth-First Search: BFS Templates and TypeScript in Practice

Table of Contents

Overview Problem Definition Core Principle: Step-by-Step Illustration Level-Order Expansion Detailed Algorithm Steps TypeScript Implementation 1. Generic BFS Template 2. Number of Islands 3. Open the Lock 4. Bidirectional BFS Engineering Optimization: Queues and Access Timing Applications and Limitations Typical Applications Limitations Summary

1047 words

5 minutes

Breadth-First Search: BFS Templates and TypeScript in Practice

2026-04-26

Algorithms

Breadth-First Search

/

BFS

/

TypeScript

/

Algorithms

Overview#

Breadth-First Search (BFS) is a traversal algorithm that expands layer by layer. Starting from the source, it first visits nodes at distance 1, then nodes at distance 2, making it naturally suited for finding the minimum number of steps in an unweighted graph.

Prerequisites

Queue: First in, first out, ensuring layer-by-layer processing

Graph / grid modeling: Treating states as nodes and single-step transitions as edges

visited set: Avoiding duplicate enqueues and infinite loops

Problem Definition#

Given a starting point and state transition rules, search for the target state in order of increasing distance.

Element	Description
Input	Start point, target, neighbor generation function or graph structure
Output	Minimum steps to reach the target, level-order result, or number of connected components
Core structure	Queue + visited set
Applicability	Every edge has equal weight, or only the minimum number of transitions matters

Core Principle: Step-by-Step Illustration#

BFS expands outward layer by layer like ripples in water:

Level-Order Expansion#

Enqueue the starting point and mark it as visited.
Each round processes only the nodes currently in the queue, which belong to the same layer.
Add unvisited neighbors to the queue as the next layer.
After processing one layer, increment the step count step + 1.

As soon as the target is encountered for the first time, the current step count can be returned, because BFS guarantees this is the shortest path.

Detailed Algorithm Steps#

1
Algorithm: BFS(start, target)
2
Input: start point start, target target
3
Output: minimum number of steps; return -1 if unreachable
4

5
1. queue ← [start]
6
2. visited ← {start}
7
3. step ← 0
8
4. while queue is not empty:
9
5.     size ← queue.length
10
6.     repeat size times:
11
7.         cur ← queue dequeue
12
8.         if cur is target, return step
13
9.         iterate over cur's neighbors next:
14
10.            if next is unvisited: mark and enqueue
15
11.    step ← step + 1
16
12. return -1

Complexity Analysis:

Scenario	Time Complexity	Space Complexity	Description
Graph traversal	O(V + E)	O(V)	Each vertex and edge is processed at most once
Grid BFS	O(mn)	O(mn)	Each cell is enqueued at most once
State search	O(number of states × branching factor)	O(number of states)	Such as combination lock, word ladder
Bidirectional BFS	Approximately O(b^(d/2))	O(b^(d/2))	Suitable when both start and end are known

TypeScript Implementation#

1. Generic BFS Template#

1
function bfs<T>(start: T, isTarget: (node: T) => boolean, getNeighbors: (node: T) => T[]): number {
2
  const queue: T[] = [start];
3
  const visited = new Set<T>([start]);
4
  let head = 0;
5
  let step = 0;
6

7
  while (head < queue.length) {
8
    const size = queue.length - head;
9

10
    for (let i = 0; i < size; i++) {
11
      const cur = queue[head++];
12
      if (isTarget(cur)) return step;
13

14
      for (const next of getNeighbors(cur)) {
15
        if (visited.has(next)) continue;
16
        visited.add(next);
17
        queue.push(next);
18
      }
19
    }
20

21
    step++;
22
  }
23

24
  return -1;
25
}

2. Number of Islands#

1
function numIslands(grid: string[][]): number {
2
  const m = grid.length;
3
  const n = grid[0].length;
4
  const dirs = [[1, 0], [-1, 0], [0, 1], [0, -1]];
5
  let count = 0;
6

7
  function floodFill(row: number, col: number): void {
8
    const queue: [number, number][] = [[row, col]];
9
    let head = 0;
10
    grid[row][col] = '0';
11

12
    while (head < queue.length) {
13
      const [x, y] = queue[head++];
14
      for (const [dx, dy] of dirs) {
15
        const nx = x + dx;
16
        const ny = y + dy;
17
        if (nx < 0 || nx >= m || ny < 0 || ny >= n || grid[nx][ny] !== '1') continue;
18
        grid[nx][ny] = '0';
19
        queue.push([nx, ny]);
20
      }
21
    }
22
  }
23

24
  for (let i = 0; i < m; i++) {
25
    for (let j = 0; j < n; j++) {
26
      if (grid[i][j] === '1') {
27
        count++;
28
        floodFill(i, j);
29
      }
30
    }
31
  }
32

33
  return count;
34
}

3. Open the Lock#

1
function openLock(deadends: string[], target: string): number {
2
  const dead = new Set(deadends);
3
  if (dead.has('0000')) return -1;
4

5
  const queue = ['0000'];
6
  const visited = new Set<string>(['0000']);
7
  let head = 0;
8
  let step = 0;
9

10
  function nextStates(state: string): string[] {
11
    const result: string[] = [];
12
    for (let i = 0; i < 4; i++) {
13
      const digit = Number(state[i]);
14
      for (const next of [(digit + 1) % 10, (digit + 9) % 10]) {
15
        result.push(state.slice(0, i) + next + state.slice(i + 1));
16
      }
17
    }
18
    return result;
19
  }
20

21
  while (head < queue.length) {
22
    const size = queue.length - head;
23

24
    for (let i = 0; i < size; i++) {
25
      const cur = queue[head++];
26
      if (cur === target) return step;
27

28
      for (const next of nextStates(cur)) {
29
        if (dead.has(next) || visited.has(next)) continue;
30
        visited.add(next);
31
        queue.push(next);
32
      }
33
    }
34

35
    step++;
36
  }
37

38
  return -1;
39
}

4. Bidirectional BFS#

1
function openLockBidirectional(deadends: string[], target: string): number {
2
  const dead = new Set(deadends);
3
  if (dead.has('0000')) return -1;
4

5
  let begin = new Set<string>(['0000']);
6
  let end = new Set<string>([target]);
7
  const visited = new Set<string>(['0000']);
8
  let step = 0;
9

10
  function nextStates(state: string): string[] {
11
    const result: string[] = [];
12
    for (let i = 0; i < 4; i++) {
13
      const digit = Number(state[i]);
14
      result.push(state.slice(0, i) + ((digit + 1) % 10) + state.slice(i + 1));
15
      result.push(state.slice(0, i) + ((digit + 9) % 10) + state.slice(i + 1));
16
    }
17
    return result;
18
  }
19

20
  while (begin.size > 0 && end.size > 0) {
21
    if (begin.size > end.size) [begin, end] = [end, begin];
22

23
    const nextLayer = new Set<string>();
24
    for (const cur of begin) {
25
      if (dead.has(cur)) continue;
26
      if (end.has(cur)) return step;
27

28
      for (const next of nextStates(cur)) {
29
        if (visited.has(next)) continue;
30
        visited.add(next);
31
        nextLayer.add(next);
32
      }
33
    }
34

35
    begin = nextLayer;
36
    step++;
37
  }
38

39
  return -1;
40
}

Engineering Optimization: Queues and Access Timing#

JavaScript array shift() shifts subsequent elements; for large queue scenarios, use a head pointer to simulate dequeuing.

Optimization Point	Recommended Practice	Reason
Dequeue	`const cur = queue[head++]`	Avoid the O(n) shifting of `shift()`
Marking visits	Mark when enqueuing	Prevent the same node from being enqueued repeatedly
Level counting	Record the current level `size`	Accurately maintain the shortest step count
Bidirectional search	Expand from the smaller frontier	Reduce the exponential state space

Applications and Limitations#

Typical Applications#

Shortest path in unweighted graphs
Level-order traversal of binary trees
Grid propagation: islands, mazes, rotting oranges
State search: combination lock, word ladder

Limitations#

Limitation	Description
High memory usage	The queue may hold an entire level of nodes
Not suitable for weighted shortest paths	When edge weights differ, algorithms such as Dijkstra should be used
State explosion	When the branching factor is large, pruning or bidirectional search is needed

Summary#

Key Points:

BFS = queue + visited + level-by-level expansion.
In an unweighted graph, the first time the target is reached is the shortest path.
For large queues, use a head pointer; do not frequently shift().
When both the start and end points are known, prioritize bidirectional BFS.