python蓝桥杯 BFS

### Python 蓝桥杯广度优先搜索 (BFS) 算法实现示例 以下是基于蓝桥杯竞赛场景下的广度优先搜索 (BFS) 算法的实现方法。此算法通常用于解决诸如最短路径、连通性等问题。 #### BFS 基本原理 广度优先搜索是一种逐层扩展节点的方式，适用于无权图中最短路径问题的求解。其核心思想是从起始点出发，逐步探索相邻节点，并记录已访问状态以防止重复计算[^1]。 #### 实现代码示例 下面是一个典型的 BFS 实现案例，假设我们需要在一个二维网格中找到从起点到终点的最短路径： ```python from collections import deque def bfs(grid, start, goal): rows, cols = len(grid), len(grid[0]) visited = [[False for _ in range(cols)] for _ in range(rows)] queue = deque([(start, 0)]) # 存储当前坐标和步数 directions = [(0, 1), (1, 0), (0, -1), (-1, 0)] # 右下左上四个方向 while queue: (current_x, current_y), steps = queue.popleft() if (current_x, current_y) == goal: return steps if not visited[current_x][current_y]: visited[current_x][current_y] = True for dx, dy in directions: next_x, next_y = current_x + dx, current_y + dy if ( 0 <= next_x < rows and 0 <= next_y < cols and grid[next_x][next_y] != '#' and not visited[next_x][next_y] ): queue.append(((next_x, next_y), steps + 1)) return -1 # 如果无法到达目标返回-1 # 测试数据 grid = [ ['.', '.', '#', '.'], ['#', '.', '.', '.'], ['.', '#', '.', '.'] ] start = (0, 0) goal = (2, 3) result = bfs(grid, start, goal) print(f"从 {start} 到 {goal} 的最少步数为: {result}") ``` 上述代码通过 `deque` 数据结构实现了队列操作，确保每次处理的是距离最近的未访问节点。同时利用布尔矩阵 `visited` 来标记哪些位置已经被访问过，从而避免冗余计算[^2]。 #### 关键点解析 1. **队列初始化**: 将初始节点加入队列，并设置初始步数为零。 2. **边界条件判断**: 对于每一个可能移动的方向，都需要验证新位置是否越界以及是否存在障碍物。 3. **终止条件**: 当前节点等于目标节点时立即返回结果；如果整个地图都被遍历完毕仍未发现目标，则返回 `-1` 表明不可达[^3]。