python 蓝桥杯bfs算法

### Python 实现蓝桥杯 BFS 算法 #### 使用队列实现广度优先搜索 (BFS) 为了在Python中实现适用于蓝桥杯竞赛的BFS算法，通常会采用队列来存储待访问节点。下面是一个基于队列的经典BFS实现方式： ```python from collections import deque def bfs(graph, start_node): visited = set() # 记录已访问过的节点集合 queue = deque([start_node]) # 初始化队列为起点 while queue: node = queue.popleft() if node not in visited: print(f'Visited {node}') # 处理当前节点的操作 visited.add(node) neighbors = graph[node] for neighbor in neighbors: if neighbor not in visited and neighbor not in queue: queue.append(neighbor) ``` 此段代码定义了一个`bfs()`函数接收两个参数：一个是表示图结构的数据字典`graph`；另一个是指定起始位置的字符串或整数形式的关键字`start_node`。 对于蓝桥杯题目而言，具体的应用场景可能涉及更复杂的逻辑处理以及特定条件下的剪枝操作等优化措施[^1]。 #### 应用实例——迷宫求解 假设有一个简单的二维数组代表迷宫地图，其中0为空地可通行，1为墙壁不可通过，则可以通过调整上述模板来进行最短路径计算： ```python maze = [ [0, 1, 0, 0, 0], [0, 1, 0, 1, 0], [0, 0, 0, 1, 0], [0, 1, 1, 1, 0], [0, 0, 0, 0, 0] ] directions = [(0,-1), (-1,0), (0,+1), (+1,0)] # 上下左右四个方向向量 def find_shortest_path(maze, start_pos, end_pos): rows = len(maze) cols = len(maze[0]) def is_valid(pos): r,c=pos return 0<=r<rows and 0<=c<cols and maze[r][c]==0 distances={start_pos:0} prev_nodes={} q=deque([(start_pos,distances[start_pos])]) while q: pos,current_distance=q.popleft() if pos==end_pos: break for d in directions: next_pos=(pos[0]+d[0],pos[1]+d[1]) if is_valid(next_pos)and next_pos not in distances: new_dist=current_distance+1 distances[next_pos]=new_dist prev_nodes[next_pos]=pos q.append((next_pos,new_dist)) path=[] current=end_pos try: while True: path.insert(0,current) if current==start_pos: break current=prev_nodes[current] except KeyError as e: pass return path if path else None ``` 这段程序实现了从给定点到目标点之间找到一条最短路径的功能，并返回由坐标组成的列表作为结果。如果不存在这样的路径则返回None[^3]。