跳转到内容

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

来自代码酷

广度优先搜索（Breadth-First Search, BFS）[编辑 | 编辑源代码]

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

基本概念[编辑 | 编辑源代码]

BFS 的核心思想是“广度优先”，即优先访问离起点最近的节点。这种策略确保在探索更深的层次之前，先完整地探索当前层次的所有节点。BFS 常用于解决以下问题：

寻找图中的最短路径（无权图）
检查图的连通性
遍历树或图的层次结构
解决迷宫问题

算法步骤[编辑 | 编辑源代码]

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

代码示例[编辑 | 编辑源代码]

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

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' 开始

输入: 邻接表表示的图：

'A' 连接 'B' 和 'C'
'B' 连接 'A', 'D', 'E'
'C' 连接 'A', 'F'
'D' 连接 'B'
'E' 连接 'B', 'F'
'F' 连接 'C', 'E'

输出:

BFS 遍历顺序:
A B C D E F

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

实际应用案例[编辑 | 编辑源代码]

最短路径问题[编辑 | 编辑源代码]

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

迷宫求解[编辑 | 编辑源代码]

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

网络爬虫[编辑 | 编辑源代码]

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

可视化示例[编辑 | 编辑源代码]

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

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

时间复杂度分析[编辑 | 编辑源代码]

BFS 的时间复杂度为 $O (V + E)$ ，其中：

$V$ 是顶点（节点）的数量
$E$ 是边的数量

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

进阶应用[编辑 | 编辑源代码]

双向 BFS[编辑 | 编辑源代码]

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

多源 BFS[编辑 | 编辑源代码]

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

总结[编辑 | 编辑源代码]

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

检索自“https://wiki.echo.cool/index.php?title=广度优先搜索（Breadth-First_Search,_BFS）&oldid=21455”

分类：