对有 n 个结点、e 条边且使用邻接表存储的有向图进行广度优先遍历,其算法时间复杂度是()。
A.O(n)
B.O(e)
C.O(n+e)
D.O(n*e)
参考答案:C
答案解析:考查...
用户登录可进行刷题及查看答案
答案解析:考查不同存储结构的图遍历算法的时间复杂度。
广度优先遍历需要借助队列实现。邻接表的结构包括:顶点表;边表(有向图为出边表)。当采用邻接表存储方式时,在对图进行广度优先遍历时每个顶点均需入队一次(顶点表遍历),故时间复杂度为O(n),在搜索所有顶点的邻接点的过程中,每条边至少访问一次(出边表遍历),故时间复杂度为 O(e),算法总的时间复杂度为 O(n+e)。
登录后提交答案
暂无评论,来抢沙发