I was looking for non-recursive implementation of DFS algorithm.

I found the following pseudocode on this page.

1  procedure DFS-iterative(G,v):
2      let S be a stack
3      S.push(v)
4      while S is not empty
5          v = S.pop()
6          if v is not labeled as discovered:
7              label v as discovered
8              for all edges from v to w in G.adjacentEdges(v) do
9                  S.push(w)

From what I understand, if we change the line 8 to be:

for all edges from v to w in G.adjacentEdges(v),if w is not discovered do

it would speed up the code, because whats the point of pushing already visited vertices on to the stack? Am I right in this assumption?

  • $\begingroup$ Have you tried it? Have you tried benchmarking the code to see how much faster it is? Have you tried running the code by hand on small examples to see what happens? I suspect you'll be able to answer your own question if you give those a try. A better question to ask is "How much more efficient would this be?" not "would it be more efficient?" $\endgroup$ – D.W. Nov 26 '16 at 18:15
  • $\begingroup$ Looks like you are right. However, this is definitely not the bottleneck place in the algorithm. Usually you perform something when discovering a node, which should be done as fast as possible. $\endgroup$ – Eugene Nov 26 '16 at 19:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.