Section 7.16 Depth-First Search Analysis
The general running time for depth-first search is as follows. The loops in not counting what happens in Therefore, the total time for depth-first search is
dfs
both run 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 You have attempted 1 of 1 activities on this page.