🧮 广度优先搜索 (BFS)

难度 / Difficulty: 中等 (Medium)
分类 / Category: 图遍历 (Graph Traversal)
时间复杂度 / Time Complexity: O(V + E)
空间复杂度 / Space Complexity: O(V)

📖 算法简介 / Introduction

广度优先搜索是一种层次遍历算法，从起点开始，先访问所有邻居节点，再向外扩展。类似于水面上的涟漪，一圈一圈向外扩散。

BFS is a level-order traversal algorithm that starts from a source node and explores all neighbor nodes first before moving to the next level of neighbors — like ripples spreading outward on water.

💡 算法原理 / Principle

1. 使用队列：从起点开始，将起点入队
2. 标记已访问：将起点标记为已访问
3. 层次扩展：从队列中取出节点，访问其所有未访问邻居并入队
4. 重复直到队列为空

核心思想：“先近后远” — 先访问距离起点最近的节点，再逐层向外。

Using a queue: start from the source node, enqueue it, then repeatedly dequeue a node and enqueue all its unvisited neighbors. The result is level-by-level exploration.

📝 代码实现 / Implementation

from collections import deque

def bfs(graph, start):
    visited = set()
    queue = deque([start])
    visited.add(start)
    
    result = []
    while queue:
        node = queue.popleft()
        result.append(node)
        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)
    return result

✨ 示例 / Example

Graph 结构：{'A': ['B', 'C'], 'B': ['D', 'E'], 'C': ['F'], 'D': [], 'E': ['F'], 'F': []}

层次遍历过程：
第1层：A
第2层：B, C
第3层：D, E, F

访问顺序：A → B → C → D → E → F

🎯 适用场景 / Scenarios

• 最短路径问题（无权图）- 找到从起点到目标的最少边数路径
• 层次遍历 - 树的层序遍历、图的层次遍历
• 社交网络好友推荐 - N度好友关系
• 迷宫问题（最少步数）
• 连通分量检测

Shortest path (unweighted graphs), Level-order traversal, Social network friend recommendations, Maze (minimum steps), Connected component detection.

🔄 与 DFS 的对比 / Comparison with DFS

🔄 扩展阅读 / Further Reading

• LeetCode 经典 BFS 题目：二叉树的层序遍历 (Binary Tree Level Order Traversal)
• 理解 BFS 在无权图最短路径中的应用
• 结合队列理解 BFS 的空间占用