Before you keep reading...
Runestone Academy can only continue if we get support from individuals like you. As a student you are well aware of the high cost of textbooks. Our mission is to provide great books to you for free, but we ask that you consider a $10 donation, more if you can or less if $10 is a burden.
Before you keep reading...
Making great stuff takes time and $$. If you appreciate the book you are reading now and want to keep quality materials free for other students please consider a donation to Runestone Academy. We ask that you consider a $10 donation, but if you can give more thats great, if $10 is too much for your budget we would be happy with whatever you can afford as a show of support.
7.16. Depth-First Search Analysis
The general running time for depth-first search is as follows. The loops
in dfs both run in ,
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 . Therefore, the total time
for depth-first search is .
You have attempted
1 of
1 activities on this page
