题4 题目 对一个有 个顶点、 条边的图采用邻接表表示时，进行 DFS 遍历的时间复杂度为 ( ) ，空间复杂度为 ( ) ；进行 BFS 遍历的时间复杂度为 ( ) ，空间复杂度为 (). A. B. C. D. 分析 DFS沿着路径遍历，一路走到黑 BFS沿着层遍历，也就是对着点的邻点遍历 我觉得是B,B,C,A 解 C、A、C、A 深度优先遍历时, 每个顶点表结点和每个边表结点均查找一次, 每个顶点递归调用一次, 需要借助一个递归工作栈; 而广度优先遍历时, 也是每个顶点表结点和每个边表结点均查找一次,需要借助一个辅助队列。 因此,时间复杂度都是 ,空间复杂度都是 。