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

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

  • O(n)
  • O(e)
  • O(n+e)
  • O(n*e)
删除与某个顶点V相关的所有边的过程:先删除下标为V的顶点表节点的单链表,出边数最多为n-1,对应时间复杂度为O(n),再扫描所以边表的结点,删除所有的顶点V的入边,对应的时间复杂度为O(e)。故总的时间复杂度为O(n+e)。选C
发表于 2019-10-11 19:16:03 回复(3)
答案是C,因为得遍历所有顶点次数为n,并且还得在e条边中找出,以Vi为端点的边,所以是O(n+e)
发表于 2020-01-03 17:31:58 回复(0)
答案是D,第一次遍历,遍历所有结点 for循环 n次,查找所有出度
第二次遍历,因为是邻接表,for循环的次数是e,看出度是否为V1,或者入度是否为V1,只要符合条件就删除边
因此,时间复杂度为O(n*e)
发表于 2019-11-26 17:32:14 回复(0)
c
编辑于 2019-12-13 19:39:53 回复(0)
O(n*e)
发表于 2019-10-05 19:41:33 回复(0)