编辑“︁广度优先搜索（Breadth-First Search, BFS）”︁（章节）

= 广度优先搜索（Breadth-First Search, BFS） =

广度优先搜索（BFS）是一种用于遍历或搜索树或图的算法。它从根节点（或任意节点）开始，逐层探索所有邻近节点，然后再移动到下一层的节点。BFS 通常使用队列（Queue）数据结构来实现，确保按照“先进先出”（FIFO）的顺序处理节点。

== 基本概念 ==

BFS 的核心思想是“广度优先”，即优先访问离起点最近的节点。这种策略确保在探索更深的层次之前，先完整地探索当前层次的所有节点。BFS 常用于解决以下问题：
* 寻找图中的最短路径（无权图）
* 检查图的连通性
* 遍历树或图的层次结构
* 解决迷宫问题

=== 算法步骤 ===
1. 将起始节点放入队列，并标记为已访问。
2. 从队列中取出一个节点，并检查其所有未访问的邻居节点。
3. 将这些邻居节点加入队列，并标记为已访问。
4. 重复步骤 2 和 3，直到队列为空。

== 代码示例 ==

以下是一个使用 Python 实现的 BFS 示例，遍历一个无向图：

<syntaxhighlight lang="python">
from collections import deque

def bfs(graph, start):
    visited = set()
    queue = deque([start])
    visited.add(start)
    
    while queue:
        node = queue.popleft()
        print(node, end=" ")  # 处理当前节点
        
        for neighbor in graph[node]:
            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' 开始
</syntaxhighlight>

'''输入:'''
邻接表表示的图：
* 'A' 连接 'B' 和 'C'
* 'B' 连接 'A', 'D', 'E'
* 'C' 连接 'A', 'F'
* 'D' 连接 'B'
* 'E' 连接 'B', 'F'
* 'F' 连接 'C', 'E'

'''输出:'''
<pre>
BFS 遍历顺序:
A B C D E F 
</pre>

'''解释:'''
1. 从 'A' 开始，访问 'B' 和 'C'（第一层）。
2. 接着访问 'B' 的邻居 'D' 和 'E'，以及 'C' 的邻居 'F'（第二层）。
3. 由于 'F' 已经被 'E' 访问过，算法终止。

== 实际应用案例 ==

=== 最短路径问题 ===
BFS 可以用于在无权图中找到两个节点之间的最短路径。例如，在社交网络中，BFS 可以计算两个人之间的最短“朋友链”。

=== 迷宫求解 ===
在网格迷宫（如二维矩阵）中，BFS 可以找到从起点到终点的最短路径。每个网格单元被视为图中的一个节点，相邻的可通行单元是邻居。

=== 网络爬虫 ===
搜索引擎的网络爬虫使用 BFS 或类似算法来系统地遍历网页链接，确保先访问距离种子页面较近的页面。

== 可视化示例 ==

以下是一个图的 BFS 遍历过程的可视化：

<mermaid>
graph TD
    A --> B
    A --> C
    B --> D
    B --> E
    C --> F
    E --> F
</mermaid>

'''遍历顺序:''' A → B → C → D → E → F

== 时间复杂度分析 ==

BFS 的时间复杂度为 <math>O(V + E)</math>，其中：
* <math>V</math> 是顶点（节点）的数量
* <math>E</math> 是边的数量

空间复杂度为 <math>O(V)</math>，因为最坏情况下需要存储所有节点（例如，当遍历一个星型图时）。

== 进阶应用 ==

=== 双向 BFS ===
双向 BFS 从起点和终点同时开始搜索，直到两个搜索相遇。这种方法可以显著减少搜索空间，适用于大规模图的最短路径问题。

=== 多源 BFS ===
多源 BFS 从多个起点同时开始搜索，常用于解决如“多个火源蔓延”或“多个起点最短路径”问题。

== 总结 ==

广度优先搜索是一种强大且直观的算法，适用于层次遍历和最短路径问题。通过队列实现，它确保按层次顺序访问节点，适合无权图的最短路径计算。理解 BFS 是学习更复杂算法（如 Dijkstra 或 A*）的重要基础。

[[Category:计算机科学]]
[[Category:数据结构与算法]]
[[Category:搜索算法]]