Question

7.16.深度优先搜索分析

深度优先搜索的一般运行时间如下。 dfs 中的循环都在 $O(V)$O(V) 中运行，不计入dfsvisit 中发生的情况，因为它们对图中的每个顶点执行一次。 在dfsvisit 中，对当前顶点的邻接表中的每个边执行一次循环。 由于只有当顶点为白色时，dfsvisit 才被递归调用，所以循环对图中的每个边或 $O(E)$O(E) 执行最多一次。 因此，深度优先搜索的总时间是 $O(V + E)$O(V+E)。