企业官网建设流程全解析

每一个刷算法题的人，都会在某一天突然撞上BFS。可能是在LeetCode上遇到一道“打开转盘锁”的题，也可能是在面试时被问到“如何计算出社交应用里两个人之间隔了几层好友”。我最初接触BFS是在解迷宫类题目时：给定一个二维网格，从左上角出发，求到达右下角需要的最少步数。当时我下意识用DFS递归硬搜，结果在中等规模的数据上直接超时。后来换成BFS，同样的数据瞬间出结果。这种反差让我印象深刻，也让我意识到：搜索类问题里，选对算法比拼命优化代码更重要。

这篇文章没有高深的理论铺垫，直接从“BFS到底是怎么工作的”“为什么它能求最短距离”“什么样的题优先用BFS”这三个角度展开，配合可运行的代码模板和几道经典题的完整拆解，帮助你把BFS从“听说过”变成“能熟练写出来”。无论你是刚接触数据结构的读者，还是准备面试需要复习搜索算法的开发者，这篇文章都适合你。

1. 从一次面试说起：为什么BFS是算法基本功

1.1 一个让我印象深刻的面试场景

有一次我参加某中厂的算法岗面试，面试官出了一道题：“给定一个由0和1组成的二维网格，0可以走，1是障碍物，从左上角出发，只能上下左右移动，问到右下角的最短路径长度是多少？”

我当时第一反应是DFS：递归遍历每一条路径，走到终点时更新最短值。但这个思路写起来麻烦且效率堪忧，在最坏情况下，一个没有障碍的网格里路径数量是按指数级增长的。面试官提醒了一句：“你要不要想想换个搜索方式？”我这才意识到应该用BFS作为主要思路。

面试官后续追问：“为什么BFS求出来的路径一定是最短路径？DFS不行吗？”这个问题让我意识到，真正掌握BFS不能只背模板，还需要理解它的层级扩展特性。

1.2 BFS的直觉理解：一圈圈扩散

BFS全称是Breadth-First Search，也就是广度优先搜索。它的核心策略是“先处理离起点最近的所有节点，再处理更远的节点”。

这是一个非常符合直觉的过程：假设你在一栋楼的中央，想知道走出这栋楼最近的大门在哪。你不会先沿着某一条走廊走到黑再折返，而是会先看看当前位置周围的几个路口，再往外推一层。这种“逐层往外扩展”的思路，就是BFS的运作方式。

起点：S 第一层：S的所有相邻节点（距离1） 第二层：所有相邻节点的相邻节点（距离2） 第三层：……以此类推

BFS按照距离分层，每一层都比上一层多一步。正因为所有节点按层级顺序被访问，所以当某个目标节点第一次被碰到时，它所在的层级数就是起点到它的最短路径长度。这个特性让BFS天然适合求解最短路径问题。

1.3 BFS在算法题里无处不在

BFS的应用远不止走迷宫：

• 树和图的层序遍历
• 无权图的最短路径（迷宫、最少步数、换乘次数）
• 多源扩散问题（腐烂的橘子、多点火源燃烧）
• 状态空间搜索（八数码、华容道、转盘锁）
• 拓扑排序中的辅助手段（Kahn算法基于BFS思想）

这些场景在LeetCode上的高频题非常多，如果搜索类题目只掌握DFS而忽视BFS，很多题会让你写得很痛苦且容易超时。

2. BFS的底层结构：队列与visited数组的配合

2.1 为什么必须用队列

BFS天然需要一个“排队处理”的数据结构。设想一下扩散过程：你先处理起点，把它所有邻居都加入待办列表，然后开始处理第一个邻居，这时要把这个邻居的邻居也加入待办列表。整个过程呈现出“先进先出”的顺序——最早加入待办列表的节点，总是先被处理。这正是队列的定义。

from collections import deque queue = deque() # 创建队列 queue.append(start) # 起点入队 while queue: node = queue.popleft() # 取出队首节点

直接用列表的pop(0)也可以，但Python列表在队首弹出时时间复杂度是O(n)，而deque的popleft()是O(1)。在数据量大的时候，这两者的性能差异非常明显。

2.2 visited数组：防止走回头路

BFS的另一个关键机制是visited数组。它记录了哪些节点已经被访问过，避免重复入队。

很多初学者漏掉这一步，写出的BFS在某些场景下不会死循环，但算法性能急剧下降，甚至出现无限循环。

visited = [[False] * cols for _ in range(rows)] visited[start_r][start_c] = True queue.append((start_r, start_c))

在图结构里，如果没有visited数组，一个环状图会让BFS永远无法退出。在网格结构里，如果没有visited数组，你会在两个格子之间来回横跳，陷入死循环。

2.3 三层思维：点、层、路径

BFS的编码过程可以用“三层思维”来拆解：

第一层：当前节点能走到哪里。从队列中取出一个节点，看看它所有合法的下一步走向。第二层：这些下一步是否值得走。判断是否越界、是否是障碍物、是否已经访问过。全部通过后，标记为已访问并加入队列。第三层：如何记录距离或路径。如果需要最短步数，就在入队时记录dist[next] = dist[current] + 1；如果还需要具体路径，就得额外保存父节点信息，在结束后回溯。

这个三层结构是BFS代码的骨架规律。无论题目如何变化，大框架都是这三件事。

3. BFS能解决的四类典型问题

3.1 网格类最短路径问题

这是最经典的分类。典型题目包括“迷宫中空房间到最近门的距离”“每个格子到最近0的距离”。

这类题目有个共同特点：给定若干起点或若干目标位置，要求计算最短距离或步数。

def bfs_grid(grid, start, target): rows, cols = len(grid), len(grid[0]) visited = [[False] * cols for _ in range(rows)] queue = deque([(start[0], start[1], 0)]) visited[start[0]][start[1]] = True # 上下左右四个方向 directions = [(-1, 0), (1, 0), (0, -1), (0, 1)] while queue: r, c, step = queue.popleft() if (r, c) == target: return step for dr, dc in directions: nr, nc = r + dr, c + dc if 0 <= nr < rows and 0 <= nc < cols and not visited[nr][nc] and grid[nr][nc] != '#': visited[nr][nc] = True queue.append((nr, nc, step + 1)) return -1 # 无法到达

这里step直接跟着队列的节点走，当节点首次出队时，它携带的步数就是最短步数。

3.2 树的层序遍历

树的BFS层序遍历是一道基础题：按层级从左到右依次输出节点值。

def level_order(root): if not root: return [] result = [] queue = deque([root]) while queue: level_size = len(queue) level_nodes = [] for _ in range(level_size): node = queue.popleft() level_nodes.append(node.val) if node.left: queue.append(node.left) if node.right: queue.append(node.right) result.append(level_nodes) return result

这个写法的巧妙之处在于：在每一轮循环开始时记录当前队列长度level_size，这个长度正好是当前层的节点数量。之后只弹出level_size个节点，就能让队列里剩下的恰好是下一层的全部节点。

树的层序遍历是很多进阶题的基础，比如二叉树的右视图、锯齿形层序遍历，底层逻辑都是这套层内处理机制。

3.3 多源BFS：同时从多个起点扩散

有些题目不止一个起点，而是多个起点同时往外扩展。比如“腐烂的橘子”问题：腐烂的橘子每分钟会传染相邻的新鲜橘子，求全部橘子腐烂需要几分钟。

这类问题的做法是把所有初始腐烂橘子同时加入队列，然后进行BFS。队列同时容纳了多个起点，BFS按照层级同时向外扩展。我在这类题目中的实战体会是：visited数组有时候可以不另开，直接用原数组标记即可，比如把腐烂的橘子标记为2，访问过的空格标记为别的值。

def oranges_rotting(grid): rows, cols = len(grid), len(grid[0]) queue = deque() fresh = 0 # 所有腐烂橘子同时入队 for i in range(rows): for j in range(cols): if grid[i][j] == 2: queue.append((i, j, 0)) elif grid[i][j] == 1: fresh += 1 max_minutes = 0 directions = [(-1, 0), (1, 0), (0, -1), (0, 1)] while queue: r, c, minutes = queue.popleft() max_minutes = max(max_minutes, minutes) for dr, dc in directions: nr, nc = r + dr, c + dc if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == 1: grid[nr][nc] = 2 fresh -= 1 queue.append((nr, nc, minutes + 1)) return max_minutes if fresh == 0 else -1

多源BFS的代码和单源BFS几乎完全一样，唯一区别是初始入队的不只一个节点。

3.4 状态空间搜索：把每一步变化看作一个“位置”

这是BFS比较进阶的用法，常见于八数码、华容道、打开转盘锁这类题。这类问题的节点不是一个坐标，而是一个完整的状态，比如一个字符串"0000"到"8888"的变化路径。

以打开转盘锁为例，每个状态可以变成8种新状态（四位数字每一位±1），从"0000"开始，找到目标状态的最少旋转次数。代码结构和网格BFS完全一样，只是“方向数组”换成了状态转换函数。

def openLock(deadends, target): dead = set(deadends) if "0000" in dead: return -1 queue = deque([("0000", 0)]) visited = {"0000"} while queue: state, turns = queue.popleft() if state == target: return turns for i in range(4): for delta in (-1, 1): digit = int(state[i]) new_digit = (digit + delta) % 10 new_state = state[:i] + str(new_digit) + state[i+1:] if new_state not in dead and new_state not in visited: visited.add(new_state) queue.append((new_state, turns + 1)) return -1

做这类题需要建立一种抽象能力：把“状态的转换”当成“图的边”，把“状态的集合”当成“图的节点”。一旦你能完成这种映射，BFS的模板就能直接套用。

4. BFS的时间复杂度与空间复杂度分析

分析BFS复杂度时，关键在于搞清楚“图上到底有多少个节点”和“每个节点会引出几条边”。

4.1 时间复杂度

BFS会访问每一个未被剪枝的节点一次，并且会检查从该节点出发的所有边。因此总复杂度是O(V + E)，其中V是节点数，E是边数。

以m x n网格迷宫为例，每个格子是一个节点，最多有4条边（上下左右），边数约为4倍节点数。因此复杂度是O(m × n)。这意味着哪怕一个1000×1000的网格，BFS也只会在百万级别运算。这也是BFS在网格题里表现优异的原因。

4.2 空间复杂度

BFS最坏情况下需要把一层的所有节点都存入队列。在网格图中，最底层可能是所有节点都入队，因此空间复杂度是O(V)。

对比一下DFS的递归实现：递归深度取决于路径长度，最坏情况下是O(V)。但DFS有一个隐形成本——递归栈可能占用大量内存甚至导致栈溢出。BFS的队列空间相比之下是可控且迭代式的，不会出现栈溢出问题。

4.3 网格题为什么优先选BFS而不是DFS

DFS求最短路径的典型做法是“遍历所有路径，同时记录最短值”。在没有障碍的网格里，从左上到右下的路径数量是指数级的。DFS在这种场景下会遍历大量不可能是最短路径的绕路分支，时间消耗巨大。

BFS则不同，它每个节点只会被入队一次，天然避开重复路径带来的指数级膨胀。这个本质区别决定了：在网格最短路径问题上，BFS是可靠的首选方案。

5. BFS和DFS的选择：搜索领域两大主角的取舍

5.1 两种搜索策略的对比

5.2 具体场景的选择逻辑

如果是求两点之间的最短步数，答案是BFS。如果只是判断两个点之间是否连通，DFS代码写起来更简洁，也是合适的方案。

如果是求“从起点出发，经过一系列限制走完全部的组合”，比如“数独求解”“N皇后”“生成括号”，BFS往往力不从心，因为这类问题需要维护完整路径并回退尝试，DFS回溯更适合。

有一个容易被忽略的判断点：如果整个搜索树的深度非常深但分支很少（比如单链结构），BFS的队列会非常长而DFS几乎只用一个递归栈，此时DFS在空间上有优势。反过来，如果搜索树的深度有限但极宽，BFS可能因为要存一整层的节点而消耗较大空间，但BFS不会因递归太深而爆栈，这两种情况需要考虑权衡。

5.3 记忆化与BFS结合

有些题目单独使用BFS会重复搜索相同的子状态。比如两个不同路径到达同一个格子，如果这个格子到目标的距离是一致的，就没必要再搜一遍。用visited数组记录已访问状态，本质上就是一种记忆化。

更进阶的做法是给visited数组加“层数”信息，即dist[r][c]不再只记录是否访问，而是记录从某个起点到达该格子的最短步数。后续如果从另一个起点到达此格子的步数比已有的大，就可以直接剪掉，不再继续扩散。这种做法在多源BFS和双起点问题中很常用。

6. BFS的常见坑与优化手段

6.1 忘记标记visited导致死循环

这是最常见的问题，尤其是图结构带环的时候。下面这段代码就是隐患：

while queue: node = queue.popleft() # 没有标记当前位置已访问 for neighbor in graph[node]: queue.append(neighbor)

如果没有预先标记，A和B两个相邻节点会反复互加，形成死循环。正确做法是在节点入队时就标记visited，而不是在出队时标记。

为什么必须在入队时标记？因为如果在出队时检查visited，那同一个节点可能同时被多个邻居加入，队列里会出现大量重复节点。虽然不会死循环，但效率会下降，而且可能破坏BFS的层级顺序，导致距离计算错误。我在实际做题中就遇到过：同一个格子被反复入队后，“首次到达即最短”的性质就不再成立。

6.2 双端队列deque的导入问题

用Python写BFS需要导入collections.deque。每次写题时都要记得加这一行导入，避免运行到一半报NameError。

6.3 步数记录的两种写法

BFS记录最短步数常用的写法有两种：

第一种是把步数直接存进队列元组，比如(r, c, step)。优点是清晰直观，缺点是额外存储占空间。

第二种是用一个dist数组，每次入队时设置dist[nr][nc] = dist[r][c] + 1。优点是省去队列中额外的步数存储，在需要输出路径时也更方便。推荐后一种写法，尤其在对内存敏感的题目中更友好。

dist = [[-1] * cols for _ in range(rows)] dist[start_r][start_c] = 0 queue.append((start_r, start_c)) while queue: r, c = queue.popleft() for dr, dc in directions: nr, nc = r + dr, c + dc if 条件合法 and dist[nr][nc] == -1: dist[nr][nc] = dist[r][c] + 1 queue.append((nr, nc))

这里将dist初始化为-1，同时起到visited和距离两个作用，比单独开一个visited数组更简洁。

6.4 双向BFS：从两端同时搜索

在处理已知起点和终点的最短路径问题，并且图比较大的时候，双向BFS是常见的优化手段。它的思路是：从起点和终点同时做BFS，每次扩展节点数较少的那一端，当两端的访问区域相遇时，最短路径就找到了。

普通的BFS从起点扩散，每增加一层要处理的节点数按分支因子增长。而双向BFS从两个方向同时扩散，相遇点的深度大约只相当于单层BFS的一半，而这大大减少了扩散的节点总量。

以8皇后问题做类比：单向BFS像从起点一盏灯照亮整个房间，光照面积越来越大；双向BFS像从房间两侧各开一盏灯，两束光在中间相遇时，被照亮的区域反而小得多。节点量级大的场景，双向BFS效果显著。

6.5 剪枝：BFS的效率放大器

剪枝是指在搜索前过滤掉明显不满足条件的分支。在BFS中，常见的剪枝有：

• 越界剪枝：检查行列坐标是否在范围内
• 障碍物剪枝：跳过不可走的格子
• 访问标记剪枝：跳过已经访问过的节点
• 最优性剪枝：如果当前已经找到解，且当前步数已经大于等于最优解，不再继续扩展
• 启发式剪枝：预判某些方向大概率偏离目标，就不优先扩展（这实际上是A*算法的雏形）

剪枝这个术语在搜索类题目里非常高频。比如前面提到过的枚举算法、KMP算法、分治算法，它们各有各的“剪”法：枚举靠条件判断缩小范围，KMP靠next数组跳过已匹配的字符，而BFS靠层级顺序+访问标记避免重复劳动。理解“剪枝”的本质，就是理解“哪些分支一定不会产出更好的结果，就别浪费资源去搜”。

6.6 小技巧：用坐标状态压缩减少内存

对于网格类BFS，坐标可以压缩为一个整数，比如pos = r * cols + c。入队时只用整数，省去元组创建的开销。这在超大面积地图题中可降低内存占用和入队时间。

queue.append(r * cols + c) while queue: pos = queue.popleft() r, c = divmod(pos, cols)

不过这种写法可读性稍差，基调是为了性能。小数据量直接用元组更清晰，大规模数据再考虑压缩。

7. 从模板到实战：三道题的完整演进过程

7.1 题一：网格中离最近0的距离

题目：给定一个0/1矩阵，对每个位置，求出该位置到最近的0的距离。

这道题的常规思路是从每个1出发做BFS，但如果有17万个1，每个都做一次BFS就非常耗时。更好的解法是反过来：从所有的0同时出发做多源BFS，用一个dist数组记录每个格子到最近的0的距离。

def updateMatrix(mat): rows, cols = len(mat), len(mat[0]) queue = deque() dist = [[-1] * cols for _ in range(rows)] for i in range(rows): for j in range(cols): if mat[i][j] == 0: dist[i][j] = 0 queue.append((i, j)) directions = [(-1, 0), (1, 0), (0, -1), (0, 1)] while queue: r, c = queue.popleft() for dr, dc in directions: nr, nc = r + dr, c + dc if 0 <= nr < rows and 0 <= nc < cols and dist[nr][nc] == -1: dist[nr][nc] = dist[r][c] + 1 queue.append((nr, nc)) return dist

多源BFS的一次搜索替代了几百次单源搜索，这正是对“反向思维”的应用。这道题让我意识到很多标注“中等”的BFS题并没有想象的那么难，关键是找到正确的方向和源头。

7.2 题二：二叉树的层序遍历

树和图的BFS代码结构几乎一样，只是少了方向数组和visited检查。

很多人在树层序遍历中直接原地修改队列，导致层与层之间无法区分。正确的做法是保留层长度，如前面代码所示：进入每一轮时先记录level_size，然后再弹出节点。这样得到的结果是一个二维数组，每个子数组代表一层节点。

7.3 题三：解数独中的剪枝对比BFS的不适用性

解数独这类问题是典型的回溯题，BFS在这种场景下不适用。原因在于：数独搜索树极其巨大，BFS每一层要存储大量部分解，空间会迅速溢出。而DFS配合剪枝能迅速沿着一条路走到终点验证，失败后立即回溯，只需要O(深度)的额外空间。

这也印证了一个观点：BFS不是万能的，它解决的是“求最短/最近”的问题；DFS解决的是“是否存在合法路径/枚举所有可能”的问题。算法选择本质上是问题性质决定的。

8. BFS在工程场景中的真实应用

BFS不仅存在于算法题中，它在工程系统里发挥着相当重要的作用。以下是我在实际项目或开源框架中接触过的几个场景，分享出来供参考。

8.1 社交网络中的好友推荐与关系度数

在社交场景中，“两个人之间隔了几层好友关系”是常见图应用。以当前用户为起点做BFS，第一层是直接好友，第二层是好友的好友，依此类推。通过控制BFS层数，可以限制搜素范围。这就是“六度分隔”理论的实际应用。

实际实现时需要注意：一个大用户的邻居数量级可能在几千到几万，如果BFS队列不加控制，内存会迅速增长。常见做法是限制最大层数并配合访问标记裁剪无关分支。

8.2 地图导航中的绕障与等权最短路径

游戏或服务中的平面地图寻路，当移动成本全部相等时，BFS可以得到和Dijkstra一致的准确最短路径，但实现更简单。我在一个简化版智能路径规划Demo中，用BFS给出所有房间到最近出口的路径，效果很不错。

如果地图上引入了不同地形成本和距离权重，需要使用的就是Dijkstra或A算法。BFS假设每条边权重相同，而A则利用启发函数引导搜索方向，因此效率比BFS更高。BFS在无权重场景下仍然是首选方案。

8.3 网络广播与信息扩散

在P2P网络或消息推送系统中，广播信息的传递本质上就是BFS的逐层扩散模型。每个节点收到消息后转发给邻居，邻居再转发给它们的邻居。BFS的思想指导着消息的TTL设置（最大转发层数），防止消息在网络中无限传播。

这种场景中有一个工程细节：消息广播很容易产生冗余重复转发，发送方和接收方需要维护已处理消息的哈希集合。这套机制与visited数组的逻辑如出一辙。

8.4 游戏AI的状态空间搜索

一些简单游戏AI会枚举所有可能状态，选择最优动作。例如井字棋AI可以通过BFS枚举所有状态空间来预判输赢。RPG游戏里的NPC寻路如果地图是栅格化的且没有地形权重，BFS可以直接计算出绕过障碍的路径。实际游戏里还会结合A*甚至JPS（跳点搜索）来优化性能，但它们的基础思想都是从BFS发展出来的。

9. 学习BFS的路径建议与刷题顺序

9.1 第一阶段：把模板背熟

先熟练掌握无向图/树的BFS模板，能流畅写出队列+visited的核心结构。建议亲手写至少三遍标准模板，直到不看书也能快速写出正确代码。

9.2 第二阶段：网格题专项训练

这一阶段主要刷网格遍历类题目：岛屿数量、岛屿最大面积、腐烂的橘子、01矩阵。这些题可以让你把方向数组、visited、步数记录这些技巧练到肌肉记忆。

实战经验：先自己做一遍，再看题解。很多题用DFS也能通过，但建议主动强制自己用BFS写一遍，对比两种方法的差异，这样才能真正理解BFS的适用边界。

9.3 第三阶段：状态压缩与多维BFS

开始接触需要记录多个状态的BFS，比如“最短路径中不能连续穿过某个节点”“带钥匙的迷宫”等。这类题让visited数组多一维或多层状态，代码量增大，但核心框架不变。

9.4 第四阶段：图论与其他算法的交叉

把BFS和拓扑排序（Kahn算法）、Dijkstra、动态规划放在一起分析。观察它们之间的联系和区别，尤其注意Dijkstra其实就是在带权图上做“贪心版的BFS”。

我最初学KMP、分治、贪心这些算法的顺序是零散的，后来才意识到它们都属于“在某类问题上用最优策略避免冗余计算”。BFS平衡了遍历的完整性和效率，是搜索类算法里最适合入门也最值得深挖的一块基石。

10. 写在最后：我的BFS学习心得

如果只让我说一个BFS学习的经验，那就是：先让自己理解“层”的概念，再去看代码。BFS的代码模板不难背，难的是遇到一道新题时，能敏锐地判断“这题可以建模成图的层级扩散问题”。

我在刷题过程中总结出一个实用技巧：拿到一道搜索题时，先问自己三个问题——

1. 从一个状态出发，有哪些合法的下一步状态？
2. 搜索的过程中需要防止哪些重复状态？
3. 目标是什么？是最短步数、是是否存在，还是枚举全部可能？

当这三个问题都清晰了，算法选择往往已经呼之欲出：目标是最短步数就优先考虑BFS，目标是枚举全部合法答案就优先考虑DFS回溯。

最后分享一个解决迷宫问题时的小技巧：如果只求最短距离而不需要输出具体路径，使用dist数组而不是队列元组存步数。这样不仅省内存，在调试时还能直观看到每个格子的距离值，排查逻辑错误很有帮助。

再补充一点：实际做题时，如果发现BFS超时了，先别急着换算法，检查一下是否漏了关键的剪枝条件。有时候一行不起眼的边界判断，就能把运行时间从数秒降到几十毫秒。

希望这篇BFS算法学习笔记，能帮你跨过搜索算法的那道门槛。当你开始用“层级”的视角去看问题时，很多原本觉得困难的问题，都会变得清晰起来。