NOIP 提高组初赛 · NOIP 2015 提高组初赛试题 第 11 题

具有 $n$ 个顶点，$e$ 条边的图采用邻接表存储结构，进行深度优先遍历和广度优先遍历运算的时间复杂度均为（ ）。

这题考图遍历复杂度。拿到题先想存储结构：邻接表只存存在的边，所以访问顶点是 n，扫描边是 e，加起来就是答案。

最容易把邻接表跟邻接矩阵搞混，死记硬背成 O(n²)。其实邻接矩阵不管有没有边都得扫一行，而邻接表只扫有边的部分，所以是线性的。

考点概念：图遍历的时间复杂度

深度优先遍历（DFS） 与 广度优先遍历（BFS）：

• 每个顶点入栈/入队一次：O(n)
• 邻接表中每条边被检查一次（无向图每条边出现在两个顶点的邻接表里，共检查 2e 次）：O(e)

总时间复杂度：Θ(n + e)，选 D。

对比：用邻接矩阵存储时，确定一个顶点的所有邻接点要扫描整行，复杂度为 Θ(n²)。

命题视角：为什么考这个？

命题人喜欢拿「存储结构」做文章。图有两种主流存法：邻接矩阵和邻接表。矩阵是二维数组，不管有没有边都得扫一行，所以遍历是 O(n²)，跟边数 e 没关系；邻接表是链表数组，只存存在的边，遍历就是 O(n+e)。这题就是让你区分这两种存储的复杂度差异。

思考心法：拿到题怎么推？

1. 先看题目给的存储结构：「邻接表」。 2. 想 DFS/BFS 的过程：每个顶点进栈/进队一次 → O(n)。 3. 想边的处理：邻接表里，每条边只在对应的顶点链表里出现一次（有向）或两次（无向），但无论几次，每条边都被检查常数次 → O(e)。 4. 加起来就是 O(n+e)。

避坑提醒

千万别把邻接表当成邻接矩阵来记。很多同学背了「图遍历是 O(n²)」，一看到图就选 A。其实那是矩阵的复杂度。邻接表是 O(n+e)，只有当图是稠密图（e≈n²）时，O(n+e) 才退化成 O(n²)，但题目没说图稠密，所以不能默认。

考频与趋势

图的基本概念在题库里共考过 281 题，覆盖 11 个考试级别。逐年分布：2007 年 1 题、2008 年 2 题、2009 年 2 题、2010 年 2 题、2011 年 3 题、2013 年 3 题、2014 年 2 题、2015 年 2 题、2016 年 1 题、2017 年 3 题、2018 年 1 题、2019 年 2 题、2020 年 1 题、2021 年 4 题、2022 年 3 题、2023 年 36 题、2024 年 61 题、2025 年 58 题、2026 年 71 题、null 年 23 题。

分赛事：GESP 八级 85 题、GESP 七级 85 题、GESP 五级 36 题、GESP 六级 27 题、CSP 提高级 13 题、NOIP 普及组 初赛 12 题、NOIP 提高组 初赛 10 题、CSP 入门级 7 题、GESP 三级 3 题、GESP 一级 2 题、GESP 二级 1 题。

从数据看，2023-2026 年图相关题目数量激增（2024 年 61 题、2025 年 58 题、2026 年 71 题），说明图论是近年高频考点，尤其是存储结构与遍历复杂度的对比，几乎年年出现。

预测

基于近年趋势，未来 1-2 年仍会高频考查图遍历复杂度，大概率继续以「邻接表 vs 邻接矩阵」的对比形式出现，也可能结合「稀疏图/稠密图」的讨论，但核心结论不会变：邻接表遍历是 Θ(n+e)。暂无足够依据预测具体题型变化，但可以肯定的是，只要看到「邻接表 + 遍历」，答案就是 O(n+e)。