广度优先搜索：BFS 的模板与 TypeScript 实战

1417 字

7 分钟

广度优先搜索：BFS 的模板与 TypeScript 实战

2026-04-26

算法

广度优先搜索

/

BFS

/

TypeScript

/

算法

概述#

广度优先搜索（Breadth-First Search, BFS） 是一种按层扩展的遍历算法。它从起点出发，先访问距离为 1 的节点，再访问距离为 2 的节点，因此天然适合求无权图中的最短步数。

前置知识

队列：先进先出，保证按层处理

图 / 网格建模：把状态看成节点，把一步转移看成边

visited 集合：避免重复入队和死循环

问题定义#

给定起点和状态转移规则，按距离从近到远搜索目标状态。

要素	说明
输入	起点、目标、邻居生成函数或图结构
输出	到达目标的最少步数、层序结果或连通区域数量
核心结构	队列 + visited 集合
适用前提	每条边权重相同，或只关心最少转移次数

核心原理：分步图解#

BFS 的扩展顺序像水波纹一样一层层向外扩散：

graph TD
    S[起点 step=0] --> A[第一层 step=1]
    S --> B[第一层 step=1]
    A --> C[第二层 step=2]
    A --> D[第二层 step=2]
    B --> E[第二层 step=2]

层序扩展#

起点入队，并标记为已访问。
每轮只处理当前队列中的节点，这些节点属于同一层。
将未访问的邻居加入队列，作为下一层。
处理完一层后，步数 step + 1。

只要第一次遇到目标，就可以返回当前步数，因为 BFS 保证这是最短路径。

算法精细步骤#

1
算法：BFS(start, target)
2
输入：起点 start，目标 target
3
输出：最少步数；不可达时返回 -1
4

5
1. queue ← [start]
6
2. visited ← {start}
7
3. step ← 0
8
4. while queue 不为空：
9
5.     size ← queue.length
10
6.     重复 size 次：
11
7.         cur ← queue 出队
12
8.         如果 cur 是 target，返回 step
13
9.         遍历 cur 的邻居 next：
14
10.            如果 next 未访问：标记并入队
15
11.    step ← step + 1
16
12. return -1

复杂度分析：

场景	时间复杂度	空间复杂度	说明
图遍历	O(V + E)	O(V)	每个点和边最多处理一次
网格 BFS	O(mn)	O(mn)	每个格子最多入队一次
状态搜索	O(状态数 × 分支数)	O(状态数)	如转盘锁、单词接龙
双向 BFS	约 O(b^(d/2))	O(b^(d/2))	适合起点和终点都明确的搜索

TypeScript 实现#

1. 通用 BFS 模板#

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. 岛屿数量#

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. 打开转盘锁#

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. 双向 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
}

工程优化：队列与访问时机#

JavaScript 数组的 shift() 会移动后续元素，大队列场景应使用 head 指针模拟出队。

优化点	推荐做法	原因
出队	`const cur = queue[head++]`	避免 `shift()` 的 O(n) 移动
标记访问	入队时标记	防止同一节点被重复加入队列
分层计数	记录当前层 `size`	准确维护最短步数
双向搜索	从较小 frontier 扩展	降低指数级状态空间

应用与局限#

典型应用#

无权图最短路径
二叉树层序遍历
网格扩散：岛屿、迷宫、腐烂橘子
状态搜索：转盘锁、单词接龙

局限性#

局限	说明
内存占用高	队列可能保存整层节点
不适合带权最短路	边权不同应使用 Dijkstra 等算法
状态爆炸	分支因子大时需要剪枝或双向搜索

总结#

graph LR
    A[起点入队] --> B[处理当前层]
    B --> C[发现未访问邻居]
    C --> D[邻居入队]
    D --> E[步数加一]
    E --> B

核心要点：

BFS = 队列 + visited + 按层扩展。
无权图第一次到达目标就是最短路径。
大队列使用 head 指针，不要频繁 shift()。
起点和终点都明确时，优先考虑双向 BFS。

广度优先搜索：BFS 的模板与 TypeScript 实战

https://www.hehonglei.cn/technology/bfs/

作者

Honglei He

发布于

2026-04-26

许可协议

CC BY-NC-SA 4.0

回溯算法：从全排列到 N 皇后的 TypeScript 实现

二分搜索：从入门到边界处理精通

概述#

问题定义#

核心原理：分步图解#

层序扩展#

算法精细步骤#

TypeScript 实现#

1. 通用 BFS 模板#

2. 岛屿数量#

3. 打开转盘锁#

4. 双向 BFS#

工程优化：队列与访问时机#

应用与局限#

典型应用#

局限性#

总结#

👋 欢迎光临