我要招人

去企业版

首页 > 试题广场 >

假设一个有n个顶点和e条弧的有向图用邻接表表示，则删除与某个

[单选题]

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

```
O(n)
```
```
O(e)
```
```
O(n+e)
```
```
O(n*e)
```

RQTN

虽然是选 C，但高赞答案解释显然有问题吧。题目都说了边数为 e，怎么可能 v 的出边的数量最多为 n-1？

考虑只有 e = 1 的情况，要删除这个边，你得遍历整个顶点表，其中只有一个顶点结点的指针域是非空的，这个时间复杂度是 O(n) 级别的；再考虑整个顶点表中只有一个顶点的边表非空，且要删除的顶点恰好是该唯一的边表的最后一个，此时是 O(n+e)。

发表于 2020-08-02 12:47:09 回复(2)

牛客944648407号

错解：删除有关边，即遍历边集即可，时间复杂度为O（e）

事实上，我们要考虑最坏情况，顶点v上有e条出边，其他顶点无出边的情况，仍需扫描n个节点寻找入边，故时间复杂度为O（n），扫描出边为O（e），故总共为O(n+e)，选C

发表于 2021-07-26 21:00:20 回复(0)

ヤ哭，已無淚〆

答案是C，因为得遍历所有顶点次数为n，并且还得在e条边中找出，以Vi为端点的边，所以是O(n+e)

发表于 2020-01-03 17:31:58 回复(0)

一朵小云彩

删除与某个顶点V相关的所有边的过程：先删除下标为V的顶点表节点的单链表，出边数最多为n-1，对应时间复杂度为O（n），再扫描所以边表的结点，删除所有的顶点V的入边，对应的时间复杂度为O(e)。故总的时间复杂度为O(n+e)。选C

发表于 2019-10-11 19:16:03 回复(11)

要进大厂大厂的橘子

答案是D，第一次遍历，遍历所有结点 for循环 n次，查找所有出度
第二次遍历，因为是邻接表，for循环的次数是e，看出度是否为V1，或者入度是否为V1，只要符合条件就删除边
因此，时间复杂度为O（n*e）

发表于 2019-11-26 17:32:14 回复(2)

jfjdjdjs

编辑于 2019-12-13 19:39:53 回复(0)

牛牛客客牛牛

第一次遍历，遍历所有结点 for循环 n次，查找所有出度第二次遍历，因为是邻接表，for循环的次数是e，看出度是否为V1，或者入度是否为V1，只要符合条件就删除边因此，时间复杂度为O（n*e）

发表于 2023-12-20 20:49:18 回复(0)

BruceAlexis

加个条件e>n

发表于 2021-06-23 01:07:20 回复(0)

牛客252752239号

应该是扫描v的所有邻接点一个一个删除是O（n）

然后扫描所有的边，删掉与v 有关的边是O(e）两个加起来就好了所以是C

发表于 2020-12-05 21:54:34 回复(0)

华丽的外套

为啥不是B，直接遍历所有边表，只要带v的全删了

发表于 2020-07-30 20:16:24 回复(2)

天尊墨宇

选C
删除与某个顶点V相关的所有边的过程：先删除下标为V的顶点表结点的单链表，出边数最多为n-1，对应时间复杂度为O（n），再扫描所以边表的结点，删除所有的顶点V的入边，对应的时间复杂度为O(e)。故总的时间复杂度为O(n+e)。

编辑于 2020-07-12 10:19:19 回复(0)

Donny20190915200238

O（n*e）

发表于 2019-10-05 19:41:33 回复(0)

提交观点

问题信息

图

上传者：城市里的养猫者

难度：

12条回答 14收藏 14023浏览

假设一个有n个顶点和e条弧的有向图用邻接表表示，则删除与某个

问题信息

热门推荐

相关试题