Когда отмечать посещение в итеративном 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"

Изменить:
Маркировка при pop действительно может быть предпочтительным способом для dfs, если мы также решим «проверить посещение» при pop. Вместо того, чтобы проверять соседей 

Код: Выделить всё

if not nbr in visited:

, вместо этого мы можем проверить узел, который будет расширен, с помощью if not now in visited:. По сравнению с моим исходным кодом проверки посещения при push, проверка посещения при pop кажется более безопасной и правильной, потому что мы просто не расширяем его, а перед этим все равно добавляем в стек. Причина, по которой мы отмечаем посещенные как популярные, заключается в том, как сказал @MattTimmermans.

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