BFS

BFS（广度优先搜索，Breadth-First Search）是一种用于遍历或搜索树或图的算法。它的核心思想是从起始节点开始，逐层向外扩展，先访问离起始节点最近的节点，再访问更远的节点。BFS通常使用队列（Queue）来实现。

BFS的核心思想

1. 逐层扩展：

   • 从起始节点开始，先访问所有与起始节点直接相连的节点（第一层）。
   • 然后访问与第一层节点相连的节点（第二层），依此类推。

2. 队列的使用：

   • 使用队列来存储待访问的节点。
   • 每次从队列中取出一个节点，访问其所有未访问的邻居节点，并将这些邻居节点加入队列。

3. 避免重复访问：

   • 使用一个集合或数组来记录已访问的节点，确保每个节点只被访问一次。

BFS的步骤

1. 初始化：

   • 将起始节点加入队列，并标记为已访问。

2. 遍历队列：

   • 从队列中取出一个节点，访问该节点。
   • 将该节点的所有未访问的邻居节点加入队列，并标记为已访问。

3. 重复直到队列为空：

   • 继续上述过程，直到队列为空，表示所有可达节点都已访问。

BFS的实现

以下是BFS的Python实现：

from collections import deque

def bfs(graph, start):
    visited = set()  # 记录已访问的节点
    queue = deque([start])  # 使用队列存储待访问的节点
    
    while queue:
        node = queue.popleft()  # 取出队列中的第一个节点
        if node not in visited:
            print(node)  # 访问当前节点（例如打印）
            visited.add(node)  # 标记为已访问
            # 将所有未访问的邻居节点加入队列
            for neighbor in graph[node]:
                if neighbor not in visited:
                    queue.append(neighbor)

# 示例调用
graph = {
    'A': ['B', 'C'],
    'B': ['D', 'E'],
    'C': ['F'],
    'D': [],
    'E': ['F'],
    'F': []
}
bfs(graph, 'A')

BFS的输出

对于上述图：

1. queue = [A], pop(A), queue = [B, C], visited = [A]
2. pop(B), queue = [C, D, E], visited = [A, B]
3. pop(C), queue = [D, E], visited = [A, B, C]
4. pop(D), queue = [E], visited = [A, B, C, D]
5. pop(E), queue = [F], visited = [A, B, C, D, E]
6. pop(F), queue = [], visited = [A, B, C, D, E, F]

BFS的输出结果为：

A
B
C
D
E
F

BFS的特点

1. 时间复杂度：

   • 邻接表表示：O(V + E)，其中V是节点数，E是边数。
   • 邻接矩阵表示：O(V²)。

2. 空间复杂度：

   • O(V)，取决于队列的大小。

3. 适用场景：

   • 寻找最短路径（在无权图中）。
   • 层级遍历树或图。
   • 检测图中是否存在环。
   • 解决迷宫问题。

BFS的应用示例

1. 寻找最短路径（无权图）

• 在无权图中，BFS可以找到从起始节点到目标节点的最短路径（最少边数）。

2. 层级遍历

• 对树或图进行层级遍历，逐层访问节点。

3. 检测图中是否存在环

• 在无向图中，如果BFS过程中遇到一个已经访问过的节点，并且该节点不是当前节点的父节点，则说明图中存在环。

BFS与DFS的区别

总结

BFS是一种基于队列的图遍历算法，适合解决需要逐层扩展的问题，如寻找最短路径、层级遍历等。它的实现简单直观，是图论中最基础的算法之一。