跳转至

7.16.深度优先搜索分析

7.16.深度优先搜索分析

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