• 7.16.深度优先搜索分析

    7.16.深度优先搜索分析

    深度优先搜索的一般运行时间如下。 dfs 中的循环都在

     7.16.深度优先搜索分析  - 图1 中运行,不计入dfsvisit 中发生的情况,因为它们对图中的每个顶点执行一次。 在dfsvisit 中,对当前顶点的邻接表中的每个边执行一次循环。 由于只有当顶点为白色时,dfsvisit 才被递归调用,所以循环对图中的每个边或 7.16.深度优先搜索分析  - 图2 执行最多一次。 因此,深度优先搜索的总时间是 7.16.深度优先搜索分析  - 图3