Существует ли «официальная» или даже правильная реализация DFS?

Question

В этом вопросе указан псевдокод для DFS:

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)

Тем не менее, он обладает очень яркими деталями - один и тот же узел может быть - и часто будет - помещен в стек дважды !!!!!!

               1
               | \
               |  2
               | /
               3

Push 1

Pop 1

Добавить 1 к посещенным

Push 2, 3

Pop 2

Добавить 2 к посещенным

НАЖМИТЕ 1, ЧТОБЫ СТЕКАТЬ СНОВА

...

...

Конечно, это не может быть правдой ??

Answer 1

Вы правы, говоря, что узел 1 снова будет помещен в стек. Но это не имеет значения: в основном оно будет проигнорировано на следующем проходе, потому что оно уже помечено как «посещенное»:

if (current is in visited):
    continue

Кроме того, вы можете добавить узел в стек только в том случае, если он еще не посещен:

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

Не исключено, что вы добавите эту проверку в практическую реализацию. Но код является псевдокодом, и он часто пишется в очень общей форме, где такого рода «оптимизация» или «улучшение» не учитывается ради компактности и универсальности, если алгоритм верен. И здесь разница не влияет на правильность: в обоих случаях та часть, которая говорит

// do something with current

будет выполняться только один раз для каждого узла.