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.
9.16. Depth First Search Analysis
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 dfsvisit
, since they are executed once
for each vertex in the graph. In dfsvisit
the loop is executed once for each edge in the adjacency
list of the current vertex. Since dfsvisit
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)\). So, the total time
for depth first search is \(O(V + E)\).
You have attempted
of
activities on this page