Section 10.16 Depth-First Search Analysis
The general running time for depth-first search is as follows. The loops in
dfsAll both run in \(O(|V|)\text{,}\) not counting what happens in dfs, since they are executed once for each vertex in the graph. In dfs the loop is executed once for each edge in the adjacency list of the current vertex. Since dfs is only called recursively if the vertex is unvisited, the loop will execute a maximum of once for every edge in the graph, or \(O(|E|)\text{.}\) Therefore, the total time for depth-first search is \(O(|V| + |E|)\text{.}\)
You have attempted of activities on this page.
