CSP-S 提高级 · CSP 2020 提高级第一轮 第 7 题

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

拿到题先锁定‘存储结构’和‘遍历算法’两个关键词：邻接表存图是O(n+e)的，DFS/BFS都要把每个点进一次、每条边扫一次，加起来就是答案。

最容易把邻接表跟邻接矩阵搞混，看到‘遍历’就下意识想O(n²)；或者以为DFS比BFS慢，其实两者在图上复杂度完全一样；还有学生会把无向图每条边算两次当成O(2e)，其实大O里常数系数可以忽略，还是O(e)。

考点与概念

这题考的是图的遍历时间复杂度，核心是‘存储结构决定效率’：邻接表存图时，访问一个点O(1)，找它的邻居要顺着链表走；DFS/BFS都要把每个点进一次、每条边扫一次，所以总开销是O(n+e)。

命题视角

命题人喜欢把‘邻接表’和‘邻接矩阵’放一起挖坑：矩阵要扫n²个格子，表只扫n+e个结点/边；同时喜欢用‘DFS比BFS慢’这种直觉误导，其实两者在图上复杂度完全相同。