NOIP 普及组初赛 · NOIP 2011 普及组初赛试题 第 11 题

广度优先搜索时，需要用到的数据结构是（ ）。

这题考广度优先搜索（BFS）必用的数据结构。BFS 是按层推进的，所以要用队列（FIFO）来保证先发现的节点先被处理，答案直接选 B。

学生最容易把 BFS 和 DFS 搞混：BFS 用队列（先进先出），DFS 用栈（后进先出）。如果记反了，就会误选 C（栈）。另外，题目问的是“需要用到的数据结构”，不是“辅助结构”或“哈希表”，要抓住核心——BFS 的本质是层序遍历，队列就是层序遍历的载体。

考点与概念

这道题考查的是广度优先搜索（BFS）的核心实现机制。BFS 是从起点出发，一层一层地向外扩展：先访问所有距离为 1 的邻居，再访问距离为 2 的邻居，依此类推。要做到“按层处理”，就必须保证先发现的节点先被访问。这种“先进先出”（FIFO）的行为，正是队列（Queue）的本质特征。

命题视角：为什么考队列？

命题人喜欢用这种“概念对应”题来检验学生是否真正理解算法背后的数据结构选择逻辑，而不是死记硬背。BFS 和 DFS 是图论中最基础的两种搜索策略，它们分别对应两种完全不同的遍历顺序：

• BFS → 队列 → 逐层扩展 → 适合求最短路径（无权图）
• DFS → 栈（或递归）→ 一条路走到底 → 适合拓扑排序、连通性判断等

如果学生只记住了“BFS 用队列”这个结论，而没有理解“为什么”，很容易在遇到变式题（比如问“不用队列能否实现 BFS？”）时掉坑。这道题就是典型的“挖坑”：选项里有链表、散列表等看似相关的数据结构，但只有队列是 BFS 的唯一必要结构。