一、什么是BFS广度优先搜索广度优先搜索Breadth-First Search简称BFS是一种用于遍历或搜索树或图的算法。它的核心思想是从起始节点开始逐层向外扩展先访问当前节点的所有相邻节点再访问下一层的节点。二、BFS的核心特点层序遍历按照距离起始节点的层次顺序进行访问队列数据结构使用队列Queue来存储待访问的节点最短路径在无权图中BFS能找到从起点到目标节点的最短路径避免重复访问需要记录已访问节点防止无限循环三、BFS算法步骤将起始节点加入队列并标记为已访问当队列不为空时重复以下步骤从队列中取出队首节点访问该节点根据具体问题进行处理将该节点的所有未访问的相邻节点加入队列并标记为已访问队列为空时算法结束四、Python实现BFS4.1 基础BFS实现图遍历from collections import deque def bfs(graph, start): 广度优先搜索遍历图 :param graph: 邻接表表示的图{节点: [相邻节点列表]} :param start: 起始节点 :return: 访问顺序列表 visited set() # 记录已访问节点 queue deque([start]) # 使用双端队列作为队列 visited.add(start) result [] while queue: node queue.popleft() # 从队列左侧取出节点 result.append(node) # 访问节点 # 遍历相邻节点 for neighbor in graph.get(node, []): if neighbor not in visited: visited.add(neighbor) queue.append(neighbor) return result 示例图 graph { A: [B, C], B: [A, D, E], C: [A, F], D: [B], E: [B, F], F: [C, E] } 从节点A开始BFS遍历 print(BFS遍历顺序:, bfs(graph, A)) 输出: BFS遍历顺序: [A, B, C, D, E, F]4.2 带路径记录的BFS最短路径from collections import deque def bfs_shortest_path(graph, start, target): 使用BFS寻找最短路径 :param graph: 邻接表表示的图 :param start: 起始节点 :param target: 目标节点 :return: 最短路径列表如果不存在则返回None if start target: return [start] visited {start} queue deque([(start, [start])]) # (当前节点, 到达该节点的路径) while queue: current_node, path queue.popleft() for neighbor in graph.get(current_node, []): if neighbor target: return path [neighbor] if neighbor not in visited: visited.add(neighbor) queue.append((neighbor, path [neighbor])) return None # 没有找到路径 测试最短路径 graph { A: [B, C], B: [A, D, E], C: [A, F], D: [B], E: [B, F], F: [C, E, G], G: [F] } path bfs_shortest_path(graph, A, G) print(f从A到G的最短路径: {path}) 输出: 从A到G的最短路径: [A, C, F, G]五、BFS的应用场景5.1 迷宫寻路问题from collections import deque def bfs_maze(maze, start, end): 在迷宫中寻找最短路径 :param maze: 二维列表0表示可通行1表示障碍 :param start: 起始坐标 (x, y) :param end: 目标坐标 (x, y) :return: 最短路径长度和路径 if maze[start[0]][start[1]] 1 or maze[end[0]][end[1]] 1: return -1, None rows, cols len(maze), len(maze[0]) directions [(0, 1), (1, 0), (0, -1), (-1, 0)] # 右、下、左、上 visited [[False] * cols for _ in range(rows)] queue deque([(start[0], start[1], 0, [start])]) # (x, y, 步数, 路径) visited[start[0]][start[1]] True while queue: x, y, steps, path queue.popleft() if (x, y) end: return steps, path for dx, dy in directions: nx, ny x dx, y dy if (0 nx rows and 0 ny cols and maze[nx][ny] 0 and not visited[nx][ny]): visited[nx][ny] True queue.append((nx, ny, steps 1, path [(nx, ny)])) return -1, None # 没有找到路径 示例迷宫 (0可通行1障碍) maze [ [0, 1, 0, 0, 0], [0, 1, 0, 1, 0], [0, 0, 0, 1, 0], [1, 1, 0, 0, 0], [0, 0, 0, 1, 0] ] steps, path bfs_maze(maze, (0, 0), (4, 4)) print(f最短路径步数: {steps}) print(f路径: {path})5.2 二叉树的层序遍历from collections import deque class TreeNode: def init(self, val0, leftNone, rightNone): self.val val self.left left self.right right def level_order_traversal(root): 二叉树的层序遍历BFS :param root: 二叉树根节点 :return: 层序遍历结果列表 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 构建示例二叉树 1 / \ 2 3 / \ \ 4 5 6 root TreeNode(1) root.left TreeNode(2) root.right TreeNode(3) root.left.left TreeNode(4) root.left.right TreeNode(5) root.right.right TreeNode(6) print(二叉树层序遍历:, level_order_traversal(root)) 输出: [[1], [2, 3], [4, 5, 6]]六、BFS与DFS对比特性BFS广度优先搜索DFS深度优先搜索数据结构队列Queue栈Stack或递归遍历顺序层序遍历逐层扩展深度优先一条路走到底空间复杂度O(b^d)b为分支因子d为深度O(bd)最短路径在无权图中能找到最短路径不一定是最短路径适用场景最短路径、层序遍历、连通分量拓扑排序、路径存在性、回溯问题实现方式迭代队列递归或迭代栈七、BFS的时间与空间复杂度分析时间复杂度O(V E)其中V是顶点数E是边数空间复杂度O(V)最坏情况下需要存储所有顶点队列最大长度在最坏情况下队列可能包含所有顶点访问标记需要额外的O(V)空间来记录已访问节点八、BFS优化技巧双向BFS从起点和终点同时开始搜索相遇时停止A*算法在BFS基础上加入启发式函数优先搜索最有希望的节点层级记录在队列中同时记录节点和层级避免重复计算剪枝优化根据问题特性提前排除不可能的分支九、常见面试题二叉树的层序遍历LeetCode 102岛屿数量LeetCode 200打开转盘锁LeetCode 752单词接龙LeetCode 127腐烂的橘子LeetCode 994十、总结BFS是一种基础且重要的图遍历算法特别适合解决最短路径问题和层序遍历问题。掌握BFS的关键在于理解队列的使用和访问标记的重要性。在实际应用中需要根据具体问题灵活调整BFS的实现方式并注意时间和空间复杂度的平衡。学习建议从基础图遍历开始理解BFS的核心流程练习迷宫问题和二叉树层序遍历尝试解决LeetCode上的BFS相关题目理解BFS与DFS的区别和适用场景