题15 题目 Q:【2012 统考真题】对有 个顶点、 条边且使用邻接表存储的有向图进行广度优先遍历, 其算法的时间复杂度是 ( ). A. B. C. D. 分析 A:广度优先遍历需要借助队列实现。采用邻接表存储方式对图进行广度优先遍历时, 每个顶点均需入队一次 (顶点表遍历),所以时间复杂度为 ,在搜索所有顶点的邻接点的过程中,每条边至少访问一次 (出边表遍历),所以时间复杂度为 ,算法总的时间复杂度为 。 解 C