NOIP 提高组初赛 · NOIP 2011 提高组初赛试题 第 5 题

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

BFS 的核心就是按层扩散，拿到题先想‘怎么保证先访问的节点先被扩展’，答案自然指向 FIFO 的队列。

学生常把 BFS 和 DFS 搞混，记住：DFS 是‘一条路走到黑’，靠栈（或递归）回溯；BFS 是‘一圈一圈往外推’，必须靠队列。命题人最爱在选项里塞个‘链表’或‘散列表’，让你犹豫——链表只是存储方式，散列表用于加速查找，都不是控制遍历顺序的关键。再比如，有人以为队列和栈只是名字不同，其实 FIFO 和 LIFO 决定了完全不同的搜索形态，选错就全盘皆输。

考点定位：本题考查的是图搜索算法中数据结构与遍历顺序的对应关系，核心就是 BFS 必须用队列。

概念拆解：广度优先搜索（BFS）是从起点开始，一层一层地向外扩展。每一层的所有节点都被访问完，才去访问下一层。要实现这种“先访问的节点先被扩展”的规律，数据结构必须遵循先进先出（FIFO）原则——这正是队列的本质。

命题视角：命题人出题时，往往喜欢把相似概念混在一起，比如把“链表”“栈”“散列表”都放进选项，考察你是否真正理解每种结构在搜索中的角色。链表只是存储节点的一种方式，并不决定遍历顺序；散列表用于快速查找，也不是 BFS 的必备；而栈（LIFO）是 DFS 的灵魂，选错就彻底跑偏了。

思考心法：拿到题，先问自己：BFS 要按层走，那每一层的节点必须按顺序被处理，谁先被加入搜索空间，谁就先被扩展。这只能是队列。然后对比 DFS：DFS 是深入到底再回溯，天然适合用栈或递归实现。这样一对比，答案就呼之欲出了。

计算/推导：BFS 的伪代码里，初始化时把起点入队；每次循环出队一个节点，遍历其邻接点，未访问的入队。整个过程完全依赖队列的 FIFO 特性，保证每一层节点按顺序被处理，从而实现按层遍历。

避坑提醒：最容易错的是把 BFS 和 DFS 搞混，或者被“链表”“散列表”这种干扰项迷惑。记住：BFS = 队列 = FIFO = 按层；DFS = 栈 = LIFO = 深入。再比如，有人以为队列和栈只是名字不同，其实它们的操作顺序决定了完全不同的搜索形态，选错就全盘皆输。

考频与趋势：BFS 是历年初赛高频考点，题库共考过 35 题，覆盖 8 个考试级别（2011-2026）。逐年分布：2011 年 2 题、2012 年 1 题、2020 年 2 题、2021 年 1 题、2022 年 2 题、2023 年 5 题、2024 年 8 题、2025 年 6 题、2026 年 7 题、null 年 1 题。分赛事：GESP 七级 12 题、GESP 八级 9 题、CSP 提高级 5 题、GESP 六级 4 题、NOIP 提高组 初赛 2 题、CSP 入门级 1 题、GESP 五级 1 题、NOIP 普及组 初赛 1 题。从数据看，2023 年后 BFS 相关考点明显增多，尤其在 GESP 七级和 CSP 提高级中占据重要位置。

预测：基于近年考频上升趋势和 GESP 七级的高占比，预计未来几年 BFS 仍将是初赛必考内容，且更可能结合具体图结构（如无权最短路径、连通分量）出题，考察队列操作细节或与其他算法（如 Dijkstra）的对比。暂无足够依据预测具体题型变化，但掌握“BFS=队列”这一核心对应关系是应对所有变体的基础。