NOIP 提高 2015 第一轮 第 11 题：具有n个顶点，é条边的图采用邻接表存储结构，进行深度优先遍历和广度优先遍历运

题目

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

选项

• A. $\Theta(n^2)$
• B. $\Theta(e^2)$
• C. $\Theta(ne)$
• D. $\Theta(n + e)$

答案

D

题解

考点定位

本题考「邻接表遍历复杂度」,对应大纲 4.3.3（难度【1】）。

解题过程

邻接表 DFS/BFS：每点访问一次 + 每边扫一次 = Θ(n+e)。

选 D。

易错提醒

① 矩阵存储则 Θ(n²)；② 无向图邻接表存 2e 项但量级不变。