python广度搜索蓝桥杯

### Python 实现广度优先搜索 (BFS) 的蓝桥杯题目解法 #### 广度优先搜索简介 广度优先搜索（Breadth-First Search, BFS）是一种用于图遍历或树遍历的算法。它按照层次顺序访问节点，通常借助队列来实现。在许多编程竞赛中，如蓝桥杯，BFS 是解决路径寻找、最短距离等问题的核心工具。 以下是基于 Python 的 BFS 基本框架以及如何应用于蓝桥杯中的典型问题： --- #### BFS 的基本实现 下面是一个通用的 BFS 实现模板，适用于大多数场景： ```python from collections import deque def bfs(start, goal, graph): queue = deque([(start, 0)]) # 初始化队列，存储当前节点及其步数/代价 visited = set([start]) # 记录已访问过的节点 while queue: current, cost = queue.popleft() # 取出队首元素 if current == goal: # 如果到达目标节点，则返回结果 return cost for neighbor in graph[current]: # 遍历相邻节点 if neighbor not in visited: # 若未访问过该邻居节点 visited.add(neighbor) # 将其标记为已访问 queue.append((neighbor, cost + 1)) # 加入队列并更新成本 return -1 # 如果无法达到目标节点，返回 -1 表示无解 ``` 上述代码展示了标准 BFS 的逻辑结构，其中 `graph` 是邻接表形式表示的图数据结构[^2]。 --- #### 蓝桥杯经典 BFS 应用实例 ##### **题目描述** 假设有一张地图由若干个房间组成，每个房间之间可能有门相连。给定起点和终点位置，求从起点到终点所需的最少开门次数。 **输入样例：** ``` 5 4 1 2 2 3 3 4 4 5 ``` **解释：** 共有 5 个房间，编号分别为 1 到 5；第 2 至第 5 行每行两个整数 u 和 v，表示房间 u 和房间 v 之间存在一扇门。 **输出样例：** ``` 4 ``` **解答思路：** 此题可以通过构建一张无向图来模拟房间之间的连接关系，并利用 BFS 找到从起点到终点的最短路径长度。 **具体实现：** ```python from collections import defaultdict, deque # 构建图 n, m = map(int, input().split()) graph = defaultdict(list) for _ in range(m): u, v = map(int, input().split()) graph[u].append(v) graph[v].append(u) # 定义 BFS 函数 def find_min_steps(graph, start, end): queue = deque([(start, 0)]) visited = set([start]) while queue: node, steps = queue.popleft() if node == end: return steps for neighbor in graph[node]: if neighbor not in visited: visited.add(neighbor) queue.append((neighbor, steps + 1)) return -1 # 输入起始点和结束点 start, end = 1, n result = find_min_steps(graph, start, end) print(result) ``` 通过以上代码，我们可以高效计算出从起点到终点所需经过的最小门数量[^3]。 --- #### 结合引用内容扩展思考 对于小蓝希望重新排列数组以最大化查询结果总和的问题[^1]，虽然与 BFS 不完全相同，但它同样涉及优化策略的选择。如果将这一理念迁移到 BFS 中，可能会涉及到动态调整权重或者自定义比较函数的情况。 例如，在某些复杂迷宫问题中，除了考虑简单的边权外，还可以引入启发式估计值（类似于 A* 算法），从而进一步提升效率。 --- ###