目录
1. 广度优先遍历（BFS）概述
广度优先搜索（Breadth-First Search, BFS）是一种 逐层遍历图或树 的算法，适用于：
- 无权图的最短路径查找
- 连通分量检测
- 网络爬虫、社交网络分析、AI 迷宫求解等
BFS 的基本思想：
- 从起始节点开始，将其标记为已访问并加入队列
- 从队列中取出一个节点，访问其所有未访问的相邻节点
- 将这些相邻节点标记为已访问并加入队列
- 重复以上步骤，直到所有可达节点都被访问
BFS 遍历的顺序类似于 水波扩散，适用于 最短路径问题。
2. BFS 算法的特点
- 时间复杂度：O(V+E)O(V + E)，其中 VV 是顶点数，EE 是边数。
- 空间复杂度：O(V)O(V)，因为需要存储访问状态和队列中的节点。
- 适用场景：
- 无权图的最短路径查找（BFS 能保证最短路径）
- 层次遍历（如二叉树的层序遍历）
- 图的连通性检测
- 迷宫寻路、网络广播、AI 搜索等
3. BFS 算法的实现
3.1 图的表示
一般使用 邻接表 存储图：
graph = {
'A': ['B', 'C'],
'B': ['A', 'D', 'E'],
'C': ['A', 'F'],
'D': ['B'],
'E': ['B', 'F'],
'F': ['C', 'E']
}
3.2 BFS 代码实现
Python 实现
from collections import deque
def bfs(graph, start):
queue = deque([start]) # 初始化队列
visited = set([start]) # 记录访问过的节点
order = [] # 存储遍历顺序
while queue:
node = queue.popleft() # 取出队列头部节点
order.append(node)
for neighbor in graph[node]:
if neighbor not in visited:
visited.add(neighbor)
queue.append(neighbor)
return order
# 示例运行
graph = {
'A': ['B', 'C'],
'B': ['A', 'D', 'E'],
'C': ['A', 'F'],
'D': ['B'],
'E': ['B', 'F'],
'F': ['C', 'E']
}
print(bfs(graph, 'A')) # ['A', 'B', 'C', 'D', 'E', 'F']
输出：
['A', 'B', 'C', 'D', 'E', 'F']
解析：
- A 入队列，访问 B, C，加入队列
- 访问 B，加入 D, E
- 访问 C，加入 F
- 依次访问 D, E, F，完成遍历
4. BFS 在无权图中的最短路径应用
BFS 适用于无权图的最短路径查找，因为它按层级扩展，保证 首次到达终点时的路径就是最短路径。
4.1 BFS 计算最短路径（Python 实现）
def bfs_shortest_path(graph, start, goal):
queue = deque([(start, [start])]) # (当前节点, 路径)
visited = set([start])
while queue:
node, path = queue.popleft()
if node == goal:
return path # 找到最短路径
for neighbor in graph[node]:
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']
}
print(bfs_shortest_path(graph, 'A', 'F')) # ['A', 'C', 'F']
时间复杂度：O(V+E)O(V + E)
空间复杂度：O(V)O(V)
5. BFS 在实际场景中的应用
5.1 迷宫寻路
在网格迷宫中寻找最短路径（假设 0 表示可通行，1 表示障碍）：
def shortest_path_maze(grid, start, goal):
rows, cols = len(grid), len(grid[0])
queue = deque([(start, [start])])
visited = set([start])
while queue:
(x, y), path = queue.popleft()
if (x, y) == goal:
return path
for dx, dy in [(-1,0), (1,0), (0,-1), (0,1)]:
nx, ny = x + dx, y + dy
if 0 <= nx < rows and 0 <= ny < cols and grid[nx][ny] == 0 and (nx, ny) not in visited:
visited.add((nx, ny))
queue.append(((nx, ny), path + [(nx, ny)]))
return None
maze = [
[0, 1, 0, 0, 0],
[0, 1, 0, 1, 0],
[0, 0, 0, 1, 0],
[1, 1, 0, 0, 0]
]
print(shortest_path_maze(maze, (0, 0), (3, 4)))
5.2 社交网络最短关系路径
BFS 可用于 社交网络分析，如计算两人之间的最短关系链（”朋友的朋友”）。
发表回复