Когда отмечать посещение в итеративном DFS? при нажатии или при нажатии ⇐ Python

[Anonymous]

Я работаю над реализацией итеративной (нерекурсивной) версии dfs. Я не понимаю, когда помечать узел как посещенный: при push или при pop.
В bfs мы отмечаем посещенный, когда помещаем его в очередь, поэтому кажется естественным, что мы должны сделать то же самое и в dfs. Насколько я понимаю, маркировка при нажатии (более ранняя стадия, чем при нажатии), также, по-видимому, уменьшает дублирование поиска, поскольку одна и та же точка будет иметь одинаковый результат и, таким образом, повышает скорость.
Однако я узнал, что более распространенным и предпочтительным способом является маркировка при нажатии. Я не мог придумать никаких преимуществ такого способа. Однако оба они должны быть в состоянии найти решение и отличаться только путями.
Так оба ли пути принимаются как правильные dfs и почему маркировка при pop предпочтительна?
пример кода для маркировки при pop:
def dfs()
visited = set()
stack.push(start)
while not stack.isEmpty():
now = stack.pop()

visited.add(now) # Mark visited at pop

if isGoal(now):
return "Found"
for nbr in find_neighbours(now):
if not nbr in visited:
stack.push(nbr)
return "NotFound"

пример кода для отметки при нажатии:
def dfs()
visited = set(start)
stack.push(start)
while not stack.isEmpty():
now = stack.pop()
if isGoal(now):
return "Found"
for nbr in find_neighbours(now):
if not nbr in visited:
stack.push(nbr)

visited.add(nbr) # Mark visited at push

return "NotFound"


Подробнее здесь: https://stackoverflow.com/questions/798 ... -or-at-pop