对有 n 个结点、e 条边且使用邻接表存储的有向图进行广度优先遍历，其算法时间复杂度是（）。
图的遍历
A. $O(n)$
B. $O(e)$
C. $O(n+e)$
D. $O(n^2)$
[tag_link]
正确答案：C
广度优先遍历
需要借助队列实现。邻接表的结构包括：顶点表；边表（有向图为出边表）。当采用邻接表存储方式时，在对图进行广度优先遍历时每个顶点均需入队一次（顶点表遍历），故时间复杂度为O(n)，在搜索所有顶点的邻接点的过程中，每条边至少访问一次（出边表遍历），故时间复杂度为O(e)，算法总的时间复杂度为O(n+e)。