首页 > 试题广场 >

对于有 n 个结点和 e 条边的图，使用邻接表存储时，遍历图

[单选题]
对于有 n 个结点和 e 条边的图，使用邻接表存储时，遍历图的时间复杂度为（） 
  • O(e^2)
  • O(n^2)
  • O(ne)
  • O(n+e)
查看答案及解析
添加回答
俊俊＋头像 俊俊＋
采用邻接表存储方式时，在对图进行遍历时每个顶点均需入队一次（顶点表遍历），故时间复杂度为 O(n) ，在搜索所有顶点的邻接点的过程中，每条边至少访问一次（边表遍历），故时间复杂度为 O(e) ，算法总的时间复杂度为 O(n+e) 。
发表于 2020-05-29 15:37:56 回复(0)
提交观点

问题信息

安卓工程师 小米集团 2020
上传者：小小
难度：
1条回答 724浏览

热门推荐

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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