首页 > 试题广场 >

设某无向图中有n个顶点e条边，则建立该图邻接表的时间复杂度为

[单选题]

设某无向图中有n个顶点e条边，则建立该图邻接表的时间复杂度为（）。 

  • O(n+e)
  • O(n^2)
  • O(ne)
  • O(n^3)
查看答案及解析
添加回答
MinorTom头像 MinorTom
用邻接矩阵构造图时，若存储的是一个无向图，则时间复杂度为O(n^2 + n*e)，其中，对邻接矩阵的初始化耗费的时间为O(n^2);
对于DFS,BFS遍历来说，时间复杂度和存储结构有关：
n表示有n个顶点，e表示有e条边。
1.若采用邻接矩阵存储，
时间复杂度为O(n^2);
2.若采用邻接链表存储，建立邻接表或逆邻接表时，
若输入的顶点信息即为顶点的编号，则时间复杂度为O(n+e);
若输入的顶点信息不是顶点的编号，需要通过查找才能得到顶点在图中的位置，则时间复杂度为O(n*e);
发表于 2022-09-05 11:24:51 回复(0)
牛客571094530号头像 牛客571094530号
邻接表的时间复杂度和节点与边有关，所以时间复杂度是o(n+e)
发表于 2020-11-23 20:28:12 回复(0)
牛客984605579号头像 牛客984605579号
A这不是空间复杂度的答案吗？
发表于 2021-04-17 20:11:38 回复(1)
牛客782693764号头像 牛客782693764号
无向图不是o(n+2e)吗，有向图不是o(n+e)吗？求解
发表于 2021-08-07 11:07:10 回复(2)
鲜土豆头像 鲜土豆
O（n+2e）?
发表于 2018-06-01 15:01:07 回复(5)
提交观点

问题信息

复杂度
上传者：阿奻_
难度：
5条回答 14379浏览

热门推荐

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号