python - 迭代DFS实现有缺陷

我一直在练习算法和数据结构。我正在尝试编写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。
你会怎么解决我知道我可以用递归来实现，但我希望迭代的解决方案接近我的版本。

最佳答案

我想你不是有意在for循环中改变tos。在dfs中，按任意顺序将所有相邻节点推送到一个堆栈上，推送完成后，取最近的一个节点，即堆栈顶部，然后继续这样做。
所以你根本不需要这条线进入你的for循环！另外，在for循环中添加了最近添加的节点之后，将弹出该节点，这不是您想要的。所以你需要在for循环之前移动tos = stack[-1]行这也很有意义，因为在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循环的头。剩下的就看你了。

关于python - 迭代DFS实现有缺陷，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/54863398/