题目

有向图 G=(V, E) 采用邻接表存储，求某点入度的时间复杂度为（）。

错因

A

误以为只要扫一遍头数组（O(|V|)）就能数出入度，没意识到入度信息不存在头数组里——必须钻进每个顶点的出边链表挨条边看终点是不是目标点。或把"出度"和"入度"混了：邻接表里某顶点的出度 = 它自己那条出边链表的长度，O(出度)；但入度散落在所有顶点的链表里，必须遍历整张表。

B

min(|V|, |E|) 取的是两者中较小者，明显比真实开销低估。可能是"看到 V 和 E 就随手取一个"，或者错以为入度查询能"提前剪枝"——实际不行，必须扫完所有边才能确认到底有几条指向 v。

C

只想到"扫所有边"这一部分开销，写成 。问题是邻接表存储中，要"扫所有边"必须先逐个访问 |V| 个头指针——即使某个顶点的出边链表为空也得过一遍。当 （极稀疏图）时，访问头数组的 开销不可忽略；此时 反而比真实开销小，是不严谨的描述。

总解析

邻接表的存储结构：一个长度为 的头指针数组，每个表头挂出该顶点的出边链表。问题在于：邻接表只直接记录出边，入边没有单独表（除非额外维护逆邻接表）。

求顶点 v 的入度：

1. 对每个顶点 i = 1..|V|，遍历 i 的出边链表；
2. 凡看到一条 (i, v) 的边，入度计数器 +1；
3. 扫完所有顶点的链表后得到入度。

开销分析（必须把两部分都算上）：

• 遍历所有 个头指针：；
• 遍历所有 条边：。

合计 ，写成等价形式 。

为什么 C 不严谨：在稠密或一般连通图中 ，此时 ，C 和 D 渐近等价；但没有这个假设时 D 才是紧的上界——比如一个只有几条边的稀疏图，扫描 个头指针的代价就主导了。

最终答案是 D。