我要招人

去企业版

首页 > 试题广场 >

对有n个顶点、e条边且采用邻接表作为存储结构的无向图进行深度

[单选题]

对有n个顶点、e条边且采用邻接表作为存储结构的无向图进行深度优先搜索遍历的时间复杂度为（）

```
O(n)
```
```
O(n2)
```
```
O(n+e)
```
```
O(e)
```

推荐

求中个奖——狗头

选C,

邻接表，存储方法跟树的孩子链表示法相类似，是一种顺序分配和链式分配相结合的储存结构。如这个表头结点所对应的顶点存在相邻顶点，则把相邻顶点依次存放于表头结点所指向的单向链表中。

使用邻接表时间复杂度为：O(N+E)

因为在扫秒时正好扫过每条边一次，每个点一次逻辑结构分为两部分:V和E集合。因此，用一个一维数组存放图中所有顶点数据;用一个二维数组存放顶点间关系(边或弧)的数据，这个二维数组称为邻接矩阵。

使用邻接矩阵时间复杂度：O(N*N)

因为在扫秒每个点时都要扫其他的n个点

编辑于 2019-10-29 14:47:20 回复(0)

秋招快结束了又重启了？

不管DFS还是BFS

邻接表：O(N+E)

邻接矩阵：O(N*N)

发表于 2018-11-07 10:49:39 回复(0)

main方法栈帧

如下图，如果按邻接表无向图深度优先遍历
则会是如下遍历过程
首先从v0开始查找，查找到v1
然后又以v1为顶点，查找与v1相连的顶点
先查到v0，但v0已经被访问(v0和v1中间的边已经被扫描过了)
就不在扫码边了
跳过v0，查到v2
同样的步骤，以v2为顶点，查到v3
v3连接的顶点全部被访问过

所以说
每条边扫描1次
每个顶点访问1次

时间复杂度为O(n + e)

个人理解，如理解有误，欢迎吐槽～

发表于 2021-11-21 09:44:51 回复(1)

白驹之过隙

选C。

深度优先遍历：从起点开始选择一条边走到下一个顶点，每到一个顶点便标记此顶点已到达。当来到一个标记过的顶点时回退到上一个顶点，再选择一条没有到达过的顶点。当回退到的路口已没有可走的通道时继续回退。

使用邻接表要扫描每个边和顶点，所以时间复杂度为：O（n+e）

发表于 2019-10-28 18:09:45 回复(0)

小苏大哥

答案选择C,

使用邻接表时间复杂度为：O(N+E)

使用邻接矩阵时间复杂度：O(N*N)

发表于 2019-10-28 15:51:59 回复(0)

Iam乙太

原来是要把每个点和每个边都经过一次呀

发表于 2023-03-20 17:38:32 回复(0)

天尊墨宇

选C,

使用邻接表时间复杂度为：O(N+E)

使用邻接矩阵时间复杂度：O(N*N)

因为在扫秒每个点时都要扫其他的n个点

发表于 2020-06-20 14:17:45 回复(0)

提交观点

问题信息

复杂度

上传者：zsw3

难度：

7条回答 141收藏 8243浏览

对有n个顶点、e条边且采用邻接表作为存储结构的无向图进行深度

问题信息

热门推荐

相关试题