具有n个顶点、e条边的图采用邻接表存储结构,进行深度优先遍历和广度优先遍历运算的时间复杂度均为

Question

具有n个顶点、e条边的图采用邻接表存储结构，进行深度优先遍历和广度优先遍历运算的时间复杂度均为(63)。

A．O(n2)

B．O(e2)

C．O(n*e)

D．O(n+e)

Answer 1

正确答案：D
解析：本题考查数据结构基础知识。深度优先和广度优先遍历图的过程实质上是对某个顶点查找其邻接点的过程，其耗费的时间取决于所采用的存储结构。当图用邻接矩阵表示时，查找所有顶点的邻接点所需时间为O(n²)。若以邻接表作为图的存储结构，则需要O(e)的时间复杂度查找所有顶点的邻接点。因此，当以邻接表作为存储结构时，深度优先搜索遍历图的时间复杂度为 O(n+e)。