首页 > 试题广场 >

对有n 个顶点、 e 条边且使用邻接表存储的有向图进行广度优

[单选题]

对有n 个顶点、 e 条边且使用邻接表存储的有向图进行广度优先遍历，其算法的时间复杂度是（ ）。 

  • O(n)
  • O(e)
  • O(n+e)
  • O(n×e)
查看正确选项
添加回答
美团到店招聘头像 美团到店招聘
对于DFS,BFS遍历来说，时间复杂度和存储结构有关：
1.若采用邻接矩阵存储，时间复杂度为O(n^2);
2.若采用邻接链表存储，时间复杂度为O(n+e);
发表于 2017-02-17 16:33:57 回复(0)
zhaobinw头像 zhaobinw
若图采用矩阵存储，则O(n×e)，若邻接表，则 O(n+e)。
第一步遍历n。
第二步，遍历e。
发表于 2016-11-29 12:07:21 回复(2)
提交观点

问题信息

图
上传者：城市里的养猫者
难度：
2条回答 9407浏览

热门推荐

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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