首页 > 试题广场 >

题目来源于王道论坛 对有n个结点、e条边且使用邻接表存

[单选题]
题目来源于王道论坛

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

  • O(n)
  • O(e)
  • O(n+e)
  • O(n*e)
添加回答
推荐
林呼头像 林呼

广度优先遍历需要借助队列实现。邻接表的结构包括：顶点表；边表（有向图为出边表）。当采用邻接表存储方式时，在对图进行广度优先遍历时每个顶点均需入队一次（顶点表遍历），故时间复杂度为O(n)，在搜索所有顶点的邻接点的过程中，每条边至少访问一次（出边表遍历），故时间复杂度为O(e)，算法总的时间复杂度为O(n+e)。

发表于 2018-09-03 20:16:26 回复(0)
main方法栈帧头像 main方法栈帧
    就拿该栗子来说
    根据我个人的理解画了1张图
    我是这么理解的
    在我的画的图里面
    有4条边，所以按指向的方向查找4次
    有4个顶点，所以读取4次节点的值
    一共O(n + e) = O(8)
    所以时间复杂度是O(n + e)
    如解释有问题，欢迎吐槽~

发表于 2021-11-20 20:46:51 回复(2)
提交观点

问题信息

复杂度
上传者：林呼
难度：
2条回答 2425浏览

热门推荐

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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