Is there an "official", or even any correct, implementation of DFS?

Question

In this question pseudocode for DFS is supplied:

DFS(source):
  s <- new stack
  visited <- {} // empty set
  s.push(source)
  while (s is not empty):
    current <- s.pop()
    if (current is in visited):
        continue
    visited.add(current)
    // do something with current
    for each node v such that (current,v) is an edge:
        s.push(v)

However, it has a very glaring detail -- the same node can -- and often will -- be pushed to the stack twice!!!!!!

Push 1

Pop 1

Add 1 to visited

Push 2, 3

Pop 2

Add 2 to visited

PUSH 1 TO STACK AGAIN

...

Surely, that can't be right??

@Marco13 You are correct. You should post your comment as an answer. — Jim Mischel, Sep 03 '18 at 15:11
Please use the *correct* tags. DFS is the Distributed File System used by Windows — Panagiotis Kanavos, Sep 03 '18 at 15:26

score 3 · Accepted Answer · answered Sep 03 '18 at 21:20

You're right with saying that node 1 will be pushed on the stack again. But this does not matter: It will basically be ignored in the next pass, because it has already been marked as "visited":

if (current is in visited):
    continue

Alternatively, you could only add the node to the stack if it has not yet been visited:

for each node v such that (current,v) is an edge:
    if (v is NOT in visited) s.push(v)

It's not unlikely that you would add this check in a practical implementation. But the code is pseudocode, and this is often written in a very generic form where this sort of "optimization" or "improvement" is left out for the sake of compactness and genericity, as long as the algorithm is correct. And here, the difference does not affect the correctness: In both cases, that part that says

// do something with current

will only be executed once for each node.

Is there an "official", or even any correct, implementation of DFS?

1 Answers1