3. 广度优先搜索(BFS)：从层层推进到最优路径

广度优先搜索，简称 BFS，是我个人非常喜欢的一种算法。为什么？因为它「老实」。它不像某些算法那样会走捷径，它是一层一层、踏踏实实地往外扩张。你想想看，这种性格在路径规划里其实特别有用——尤其是在栅格地图这种离散环境中。

我记得刚入行那会儿，有个项目需要在仓库地图里找一条最短路径。当时我第一反应就是 BFS。虽然现在有很多更花哨的算法，但 BFS 在「无权图」里找最短路径这件事上，依然是教科书级别的存在。

3.1 BFS 算法原理

BFS 的核心思想其实很简单：从起点出发，先访问所有距离为 1 的邻居，再访问所有距离为 2 的邻居，以此类推。说白了，就是「一圈一圈往外扩」。

它依赖一个关键数据结构——队列。先进先出，谁先来谁先走。这保证了我们总是先处理离起点最近的节点。

为什么会保证找到最短路径？因为 BFS 是按「层」推进的。当你第一次遇到目标节点时，那一定是最短距离。这个性质在无权图中是铁律。

3.2 BFS 在栅格地图中的实现

栅格地图说白了就是一个二维数组。每个格子要么是空地（可通行），要么是障碍物（不可通行）。BFS 在这上面跑，其实就是在做「四方向」或「八方向」的邻居遍历。

我个人习惯用四方向，因为更符合直觉。上、下、左、右，四个邻居。当然，如果你允许斜着走，那就用八方向，但要注意斜对角穿墙的问题——这个坑我踩过。

下面是一个完整的 BFS 实现，我加了详细的注释：

def bfs(grid, start, goal):
    """
    grid: 二维栅格地图，0表示空地，1表示障碍物
    start: 起点坐标 (row, col)
    goal: 终点坐标 (row, col)
    返回: 路径列表，如果找不到返回空列表
    """
    rows = len(grid)
    cols = len(grid[0])
    
    # 四方向邻居：上、下、左、右
    directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    
    # 队列：存储待访问节点
    queue = deque()
    queue.append(start)
    
    # 记录每个节点的父节点，用于回溯路径
    parent = {start: None}
    
    # 记录已访问节点
    visited = set()
    visited.add(start)
    
    while queue:
        current = queue.popleft()
        
        # 到达目标，回溯路径
        if current == goal:
            path = []
            while current is not None:
                path.append(current)
                current = parent[current]
            return path[::-1]  # 反转得到从起点到终点的路径
        
        # 遍历四个邻居
        for dr, dc in directions:
            nr, nc = current[0] + dr, current[1] + dc
            
            # 检查边界和障碍物
            if 0 <= nr < rows and 0 <= nc < cols:
                if grid[nr][nc] == 0 and (nr, nc) not in visited:
                    queue.append((nr, nc))
                    visited.add((nr, nc))
                    parent[(nr, nc)] = current
    
    # 队列为空，找不到路径
    return []

3.3 BFS 的优缺点分析

没有银弹。BFS 虽然经典，但也不是万能的。咱们客观地聊聊它的优缺点。

优点	缺点
保证找到最短路径（无权图）	空间复杂度高，需要存储大量节点
实现简单，逻辑清晰	搜索范围大，效率低
适用于小规模地图	不适用于有权图
可并行化处理	对大规模地图内存消耗大

嗯，这里要注意一点。BFS 的空间复杂度是 O(b^d)，其中 b 是分支因子（栅格地图里通常是 4 或 8），d 是搜索深度。如果地图是 1000x1000，最坏情况下 BFS 可能要存上百万个节点。这个量级，普通机器还能扛，但如果地图再大一个数量级，那就得掂量掂量了。

3.4 BFS 实战案例

光说不练假把式。咱们来看一个具体的例子。

假设有一个 5x5 的栅格地图，0 表示空地，1 表示障碍物：

grid = [
    [0, 0, 0, 0, 0],
    [0, 1, 1, 0, 0],
    [0, 0, 0, 0, 0],
    [0, 1, 0, 1, 0],
    [0, 0, 0, 0, 0]
]

start = (0, 0)
goal = (4, 4)

运行 BFS 后，得到的路径是：

[(0,0), (1,0), (2,0), (2,1), (2,2), (2,3), (3,3), (4,3), (4,4)]

你想想看，BFS 是怎么找到这条路径的？它先访问 (0,0) 的邻居，也就是 (0,1) 和 (1,0)。然后从队列里取出 (0,1)，访问它的邻居... 一层一层推进，直到碰到 (4,4)。

这个过程中，BFS 其实「不知道」目标在哪，它只是机械地往外扩。但正是这种「笨办法」，保证了第一次碰到目标时，路径一定是最短的。

好了，BFS 的内容就聊到这儿。下一章咱们会讲 Dijkstra 算法，它解决了 BFS 不能处理权重的问题。但在此之前，我建议你把 BFS 的代码亲手敲一遍，跑几个例子感受一下。代码这东西，光看是学不会的。