7.16. Depth-First Search Analysis¶
The general running time for depth-first search is as follows. The loops
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.
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|)\).
You have attempted of activities on this page