题目

对有 n 个结点、e 条边且使用邻接表存储的有向图进行广度优先遍历，其算法时间复杂度是()。

错因

A

只算了"访问顶点"的开销，忘了还要遍历每个顶点的邻接表。如果图中边很多（比如稠密图 ）， 远不能覆盖整个 BFS 的工作量。

B

只算了"扫描邻接表（边）"的开销，忘了顶点本身的入队/出队。当图很稀疏（，比如孤立点多）时， 就漏掉了顶点的访问开销。

D

把"两层操作"误以为是嵌套循环，套了乘法。但 BFS 中"访问顶点"和"扫描邻接表"是顺序执行而非嵌套——两者加起来是 ，不是相乘的 。

的复杂度对应 Bellman-Ford 算法这种" 轮、每轮检查所有边"的真嵌套结构，不适用 BFS。

总解析

BFS 在邻接表存储下的两块工作量：

1. 顶点访问：每个顶点入队 1 次、出队 1 次，每次 。总开销：

2. 邻接表扫描：每个顶点出队后，要遍历它的邻接表（即扫描它的所有出边）。所有顶点的邻接表加起来恰好是边集 一遍——

为什么不是 ？因为 BFS 不是"对每个顶点扫描所有边"，而是"每个顶点只扫描它自己的邻接表（属于它的那部分边）"。所有顶点累计扫描的边数刚好是 。

总时间复杂度 = 。

对比邻接矩阵：邻接矩阵下扫描每个顶点的邻居要走完一行 个元素（不管实际有多少邻居），总开销 。所以稀疏图用邻接表显著省时间，稠密图差距才不大。

最终答案是 C。