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

好的，我给你讲 广度优先搜索（BFS, Breadth-First Search），并配一个直观例子。

1️⃣ 什么是广度优先

广度优先搜索的特点：

1. 按层访问：先访问根节点，然后访问它的直接子节点，再访问子节点的子节点……

2. 使用队列（FIFO）：保证先入队的节点先访问。

3. 常用于：层序遍历二叉树、最短路径搜索、图的遍历等。

核心思想：先访问“广度”（当前层）再访问“深度”（下一层）。

2️⃣ 举例：二叉树层序遍历

假设有二叉树：

        1/ \2   3/ \   \4   5   6

用列表表示为：

[1, 2, 3, 4, 5, None, 6]

BFS 遍历过程

1. 初始队列：

queue = [1]

• 访问 1，加入结果 [1]

• 将左右子节点 2 和 3 入队

queue = [2, 3]

1. 访问第二层：

• 访问 2 → 结果 [2]，入队 4 和 5

• 访问 3 → 结果 [2, 3]，入队右子节点 6

queue = [4, 5, 6]

1. 访问第三层：

• 访问 4, 5, 6 → 结果 [4, 5, 6]

• 没有子节点，队列为空，结束

最终层序遍历结果：

[[1], [2, 3], [4, 5, 6]]

✅ 可以看到，先访问每一层的所有节点，再进入下一层，这就是 BFS。

如果你愿意，我可以帮你画一张 队列推进示意图，让你一眼就能看懂每一步队列里存的节点和访问顺序，非常直观。

你想让我画吗？