NOIP 提高组初赛 · NOIP 2012 提高组初赛试题 第 12 题

从顶点 $A_0$ 出发，对有向图（ ）进行广度优先搜索（BFS）时，一种可能的遍历顺序是 $A_0,A_1,A_2,A_3,A_4$。

拿到这题先别急着看选项，脑子里得有个队列：把起点A0入队，每次出队一个点，把它所有没访问过的邻居按顺序入队，出队顺序就是遍历顺序。

学生最容易犯的错误是只看第一层邻接点，以为只要A0连A1、A2就对了，却忽略了后面A1、A2分别连谁、连的顺序怎样。比如误以为B图也行，其实B里A1连的是A4，A2连的是A3，那出队顺序就会变成A0,A1,A2,A4,A3，跟题目给的顺序对不上。还有学生容易把BFS和DFS搞混，DFS是一层一层往下钻，不是按层展开，所以会选错图。

考点：广度优先搜索（BFS）的队列机制与遍历顺序。

概念：BFS的核心是“层序展开”。从起点A0开始，先把A0入队；每次从队头取出一个点，把它所有未访问过的邻居按图中给出的顺序依次入队。这样出队的序列就是遍历顺序。

命题视角：出题人喜欢在邻接表里埋“顺序坑”——图的结构可能差不多，但邻居的先后顺序不同，导致BFS结果不一样。比如图B和图D，A0都连A1、A2，但A1、A2连的邻居顺序不同，BFS结果就不同。学生如果只看出A0的邻居，就会掉进坑里。

思考心法：拿到题先画个队列，按层模拟。

• 第一层：A0入队。
• 出队A0，把它的邻居按图里顺序入队。
• 再出队第一个邻居，把它的未访问邻居按顺序入队，依此类推。
• 最后看队列出队顺序是不是A0,A1,A2,A3,A4。

逐项核对：

• 图A：A0→A1,A2；A1→A3；A2→A4。模拟：A0入队；出A0，入A1,A2；出A1，入A3；出A2，入A4；出A3（无新邻居）；出A4。顺序：A0,A1,A2,A3,A4 ✓
• 图B：A0→A1,A2；A1→A4；A2→A3。模拟：A0入队；出A0，入A1,A2；出A1，入A4；出A2，入A3；出A4；出A3。顺序：A0,A1,A2,A4,A3 ✗
• 图C：A0→A2,A1；A2→A3；A1→A4。模拟：A0入队；出A0，入A2,A1；出A2，入A3；出A1，入A4；出A3；出A4。顺序：A0,A2,A1,A3,A4 ✗
• 图D：A0→A1,A2；A1→A3；A2→A4。模拟：A0入队；出A0，入A1,A2；出A1，入A3；出A2，入A4；出A3；出A4。顺序：A0,A1,A2,A3,A4 ✓

避坑：别只看出A0的邻居就以为B、D都行，一定要把后面几层的邻居顺序也检查一遍。图B的A1连的是A4，而不是A3，这就是关键差别。

考频与趋势：BFS在题库共考过35题，覆盖8个考试级别。逐年分布：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题。可见BFS是高频考点，尤其在GESP七、八级和近年CSP提高级中占比很大。

预测：基于现有数据，BFS在未来几年仍将是初赛和GESP高年级的必考内容，命题人可能会继续用“邻居顺序陷阱”来区分学生是否真正理解队列机制。暂无足够依据预测具体年份的题目数量变化，但趋势是稳定高频。