GESP 七级 · GESP 202312 C++ 七级 第 9 题

图的广度优先搜索中既要维护一个标志数组标志已访问的图的结点，还需哪种结构存放结点以实现遍历？（ ）

这题考的是图遍历的核心数据结构。拿到题先别想代码，直接回扣定义：广度优先（BFS）是按层、由近及远访问的，这就要求待访问节点必须保持“先进先出”的顺序，否则层次就乱了。

学生最容易把 BFS 和 DFS 记混，背成“图遍历用队列或栈”，看到选项里有“双向栈”就犹豫；或者把“已访问标记数组”的功能误以为就是“存放待访问节点”的容器，去选哈希表；还有少数人看到“优先”二字就下意识选堆，其实堆是带权最短路的专属。

【考点与概念】 图的广度优先搜索（BFS）是一种按层遍历图的方法：从起点出发，先把起点加入待访问集合，然后每次取出集合中最早加入的节点，处理它的所有邻接点，若邻接点未访问则加入集合。这一过程天然要求待访问集合遵循“先进先出”（FIFO）原则，这样才能保证当前层的所有节点都被处理完，才进入下一层。

【命题视角】 命题人专门挖了“双向栈”这个坑。很多学生知道队列是 FIFO，但看到“双向”二字容易联想到 C++ 的 deque，误以为它能实现 FIFO 的遍历。实际上 deque 作为栈使用时仍是 LIFO，只有作为队列使用时才符合 BFS 需求，而题目问的是“哪种结构存放结点以实现遍历”，标准答案就是队列。此外，哈希表常被误选为“存储待访问节点”，其实它更适合存 visited 标记或邻接表；堆则完全属于 Dijkstra 或 Prim 算法的范畴。这些混淆点都是七级图论模块的高频失分陷阱。

【思考心法】 拿到题先问自己：BFS 的核心特征是什么？——按层、由近及远。要实现这一特征，待访问节点必须按“谁先加入谁先出”的顺序排列。队列正是这种结构的唯一实现。DFS 之所以用栈，是因为它要深入到底再回溯，需要“后进先出”；BFS 不需要回溯，只需要一层一层往外扩，所以必须用队列。

【避坑提醒】

• 别被“双向栈”迷惑：栈的本质是 LIFO，双向只是操作端多了，不改变顺序。
• 别把“已访问数组”和“待访问节点集合”混为一谈：数组只负责标记，不负责维护遍历顺序。
• 别看到“优先”就选堆：堆是带权场景的专属，无权 BFS 与堆无关。

【考频与趋势】 队列在题库中共考过 46 题，覆盖 9 个级别。近年分布：2023 年 2 题、2024 年 12 题、2025 年 13 题、2026 年 9 题，呈现明显上升趋势；分赛事看，GESP 六级占 31 题，七级仅 2 题。这说明队列是六级高频考点，但七级也在逐步增加相关题目。

【预测】 基于 2024-2026 队列考题数量持续攀升且六级占比极高，未来两年七级很可能继续加大队列相关题目的比重，甚至可能出现结合 BFS 与队列操作的代码阅读题。暂无足够依据预测具体题型变化，但“队列+BFS”这一组合将成为七级图论模块的必考核心。