CSP-S 2020 第一轮 第7题：具有n个顶点，é条边的图采用邻接表存储结构，进行深度优先遍历运算的

题目

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

选项

• A. $O(n+e)$
• B. $O(n^2)$
• C. $O(e^2)$
• D. $O(n)$

答案

A

题解

选 A. \(O(n+e)\)。

用邻接表进行深度优先遍历（DFS）时：

• 每个顶点访问一次，总耗时为 \(O(n)\)。
• 扫描所有顶点的邻接表：有向图中每条边扫描一次，无向图中每条边扫描两次，总耗时均为 \(O(e)\)，因为常数倍不影响时间复杂度。

所以总时间复杂度为： \[ \boxed{O(n+e)} \]

记忆：邻接表遍历为 \(O(n+e)\)，邻接矩阵遍历为 \(O(n^2)\)。