单选题 假设有n个顶点e条边的有向图用邻接表表示，则删除与某个顶点v相关的所有边的时间复杂度为______。
  • A.O(n)
  • B.O(e)
  • C.O(n+e)
  • D.O(ne)
【正确答案】 C
【答案解析】删除与某顶点v相关的所有边的过程如下：先删除下标为v的顶点表结点的单链表，出边数最多为n-1，对应时间复杂度为O(n)，再扫描所有边表结点，删除所有的入边，对应时间复杂度为D(e)。故总的时间复杂度为O(n+e)。