假设有 $n$ 个顶点 $e$ 条边的有向图用邻接表表示，则删除与某个顶点 $v$ 相关的所有边的时间复杂度为（ ）。

A. O(n) B. O(e) C. O(n+e) D. O(ne)

复杂度分析

[tag_link]

正确答案：C

在有向图的邻接表表示中，每个顶点维护一个链表存储其出边。 删除与顶点 $v$ 相关的所有边包括两部分：一是删除顶点 $v$ 的所有出边，二是删除所有指向顶点 $v$ 的入边。 删除出边只需清空顶点 $v$ 的邻接链表，时间复杂度为 $O((v))$ ，其中 $(v)\le e$ 。 删除入边则需要遍历所有顶点的邻接链表，检查每条边是否指向 $v$ ，并在找到时删除。 遍历所有链表需访问 $n$ 个顶点和 $e$ 条边，时间复杂度为 $O(n+e)$ 。 因此，总时间复杂度为 $O((v))+O(n+e)=O(n+e)$ 。