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