Дефектная итеративная реализация DFS

Question

Я практикую алгоритмы и структуры данных.И я пытаюсь написать итеративную версию DFS.

Вот мой код:

def dfsvisit_iterative(self,startVertex):
    stack = []
    stack.append(startVertex)
    startVertex.setColor('gray')
    self.time += 1
    startVertex.setDiscovery(self.time)

    while stack:
        tos = stack[-1]

        for nextVertex in tos.getConnections():
            if nextVertex.getColor() == 'white':
                nextVertex.setColor('gray')
                nextVertex.setPred(tos)
                self.time += 1
                nextVertex.setDiscovery(self.time)
                stack.append(nextVertex)
                tos = stack[-1]

        tos.setColor('black')
        self.time += 1
        tos.setFinish(self.time)
        stack.pop()

Однако он не работает, потому что я не могу обновить цикл nextVertex in tos.getConnections(): на лету, какЯ изменяю tos в нижней части цикла.

Как бы вы это исправили?Я знаю, что могу сделать это с помощью рекурсии, но я бы хотел, чтобы итеративное решение было близко к моей версии.

Answer 1

Я думаю, вы не хотите менять tos в цикле for.В DFS вы помещаете все соседние узлы в произвольном порядке в стек, а когда завершение выполняется, вы берете самый последний, то есть вершину стека, и продолжаете это делать.

Так что вам это не нужнолиния tos = stack[-1] внутри вашего цикла for вообще!Кроме того, вы добавляете узел недавно добавленный после того, как он был добавлен в ваш цикл for, а это не то, что вам нужно.Так что вам нужно переместить stack.pop() строку перед циклом for.Это также имеет смысл, поскольку в DFS вы извлекаете (удаляете) один из стека, помещаете в него соседние и повторяете.Итак, вы делаете это:

    while stack:
        tos = stack[-1]
        stack.pop()

        for nextVertex in tos.getConnections():
            if nextVertex.getColor() == 'white':
                nextVertex.setColor('gray')
                nextVertex.setPred(tos)
                self.time += 1
                nextVertex.setDiscovery(self.time)
                stack.append(nextVertex)

        tos.setColor('black')
        self.time += 1
        tos.setFinish(self.time)

То, что вы вместо этого хотели в своем вопросе:

Если по какой-либо причине (возможно, экспериментируя?) Вам нужно сделать что-то, что вы описали вваш вопрос, вы можете попробовать использовать временные tos для итерации.Например:

while stack:
        tos = stack[-1]
        temp_tos = tos

        for nextVertex in temp_tos.getConnections():
            if nextVertex.getColor() == 'white':
                nextVertex.setColor('gray')
                nextVertex.setPred(tos)
                self.time += 1
                nextVertex.setDiscovery(self.time)
                stack.append(nextVertex)
                tos = stack[-1]

Обратите внимание, что я добавил только одну строку перед циклом for и немного изменил заголовок цикла for.А остальное зависит от вас.