# Making DFS more efficient

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

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?

• 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?" – D.W. Nov 26 '16 at 18:15
• 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. – Eugene Nov 26 '16 at 19:22