首页 > 试题广场 > 假设一个有n个顶点和e条弧的有向图用邻接表表示,则删除与某个
[单选题]

假设一个有n个顶点和e条弧的有向图用邻接表表示,则删除与某个顶点V1相关的所有弧的时间复杂度是(   )。

  • O(n)
  • O(e)
  • O(n+e)
  • O(n*e)
B. 邻接矩阵是O(n), 邻接表是O(e)
编辑于 2019-10-05 17:42:01 回复(0)
删除与某个顶点V相关的所有边的过程:先删除下标为V的顶点表节点的单链表,出边数最多为n-1,对应时间复杂度为O(n),再扫描所以边表的结点,删除所有的顶点V的入边,对应的时间复杂度为O(e)。故总的时间复杂度为O(n+e)。选C
发表于 2019-10-11 19:16:03 回复(0)
O(n*e)
发表于 2019-10-05 19:41:33 回复(0)