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

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

[tag_link]

正确答案：C

结论

答案为 C：删除与 v 相关的全部出边和入边需要 (O(n+e))。

推导

删除 v 的出边需扫描 v 的边表，删除入边则要扫描其余顶点边表；合计最多访问全部顶点和边。

易错点

仅删除出边可近似为 (O(n))，但题目还要求删除所有入边，不能忽略全表扫描。