7.16. 深度优先搜索分析¶
7.16. Depth-First Search Analysis
深度优先搜索的总体运行时间如下。dfs 中的两个循环都在 \(O(|V|)\) 时间内运行，不包括 dfs_visit 中的操作，因为它们对图中的每个顶点执行一次。在 dfs_visit 中，循环对当前顶点的邻接列表中的每条边执行一次。由于 dfs_visit 只有在顶点是白色时才会被递归调用，因此循环最多会对图中的每条边执行一次，即 \(O(|E|)\)。因此，深度优先搜索的总时间复杂度为 \(O(|V| + |E|)\)。
The general running time for depth-first search is as follows. The loops in dfs both run in \(O(|V|)\), not counting what happens in dfs_visit, since they are executed once for each vertex in the graph. In dfs_visit the loop is executed once for each edge in the adjacency list of the current vertex. Since dfs_visit is only called recursively if the vertex is white, the loop will execute a maximum of once for every edge in the graph, or \(O(|E|)\). Therefore, the total time for depth-first search is \(O(|V| + |E|)\).
创建日期: 2024年9月9日