广度优先搜索(BFS)

广度优先搜索（Breadth-First Search，简称 BFS）是一种用于遍历或搜索树或图的算法。它从根节点（或任意节点）开始，逐层访问所有相邻节点，确保在深入下一层之前完全探索当前层的所有节点。BFS 通常借助队列实现，保证先进先出的访问顺序。

算法原理

BFS 的核心思想是“先广后深”，其步骤如下： 1. 将起始节点放入队列并标记为已访问。 2. 从队列中取出一个节点，访问其所有未访问的相邻节点，并将它们加入队列。 3. 重复步骤 2，直到队列为空。

算法的时间复杂度为 $O(V+E)$，其中 $V$ 是顶点数，$E$ 是边数。

伪代码示例

  
def BFS(graph, start):  
    visited = set()          # 记录已访问节点  
    queue = [start]          # 初始化队列  
    visited.add(start)  

    while queue:  
        node = queue.pop(0)  # 取出队列首节点  
        print(node)          # 处理节点（如打印）  
        for neighbor in graph[node]:  
            if neighbor not in visited:  
                visited.add(neighbor)  
                queue.append(neighbor)

代码示例（Python）

以下是一个完整的 BFS 实现，遍历图的节点：

  
from collections import deque  

def bfs(graph, start):  
    visited = set()  
    queue = deque([start])  
    visited.add(start)  

    while queue:  
        vertex = queue.popleft()  
        print(vertex, end=" ")  
        for neighbor in graph[vertex]:  
            if neighbor not in visited:  
                visited.add(neighbor)  
                queue.append(neighbor)  

# 示例图的邻接表表示  
graph = {  
    'A': ['B', 'C'],  
    'B': ['A', 'D', 'E'],  
    'C': ['A', 'F'],  
    'D': ['B'],  
    'E': ['B', 'F'],  
    'F': ['C', 'E']  
}  

print("BFS 遍历顺序:")  
bfs(graph, 'A')  # 输出: A B C D E F

输入输出说明

• **输入**：图的邻接表表示，起始节点为 `'A'`。
• **输出**：BFS 遍历顺序为 `A → B → C → D → E → F`。

可视化过程

graph TD A --> B A --> C B --> D B --> E C --> F E --> F

遍历顺序： 1. 访问 `A`（第 0 层）。 2. 访问 `B` 和 `C`（第 1 层）。 3. 访问 `D`、`E` 和 `F`（第 2 层）。

应用场景

BFS 的实际应用包括但不限于： 1. 最短路径问题：在无权图中找到两点间的最短路径（如迷宫求解）。 2. 社交网络分析：查找某用户的“N 度好友”。 3. 网络爬虫：按层级抓取网页。 4. 连通性检测：判断图中所有节点是否连通。

案例：迷宫最短路径

假设有一个二维矩阵表示的迷宫（`0` 为通路，`1` 为障碍），求从起点 `(0,0)` 到终点 `(n-1,m-1)` 的最短步数。

  
from collections import deque  

def shortest_path(maze, start, end):  
    rows, cols = len(maze), len(maze[0])  
    directions = [(-1,0), (1,0), (0,-1), (0,1)]  # 上下左右  
    queue = deque([(start[0], start[1], 0)])      # (x, y, 步数)  
    visited = set((start[0], start[1]))  

    while queue:  
        x, y, steps = queue.popleft()  
        if (x, y) == end:  
            return steps  
        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 (nx, ny) not in visited:  
                visited.add((nx, ny))  
                queue.append((nx, ny, steps + 1))  
    return -1  # 不可达  

maze = [  
    [0, 1, 0, 0],  
    [0, 0, 0, 1],  
    [1, 1, 0, 0],  
    [0, 0, 0, 0]  
]  
print("最短步数:", shortest_path(maze, (0,0), (3,3)))  # 输出: 7

与深度优先搜索（DFS）的对比

BFS 与 DFS 对比

特性	BFS	DFS
遍历顺序	层级优先	深度优先
数据结构	队列	栈
空间复杂度	$O(V)$（最坏）	$O(d)$（d 为深度）
适用场景	最短路径、层级遍历	拓扑排序、回溯问题

总结

BFS 是解决层级遍历和最短路径问题的高效算法，适合处理节点间距离均等的场景。理解其队列实现和层级扩展机制是掌握该算法的关键。