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

admin2015-12-30 11

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

选项 A、O(n)
B、O(e)
C、O(n+e)
D、O(n*e)

答案C

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

转载请注明原文地址:https://kaotiyun.com/show/DBRi777K

本试题收录于：计算机408题库学硕统考专业分类