Iterative 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

我想你并不是要改变你的for循环中的tos。在DFS中，您将所有相邻节点以任意顺序推送到堆栈上，当推送完成时，您将获取最新的节点，即堆栈顶部并继续执行此操作。

所以你根本不需要在你的for循环中使用这行tos = stack[-1]！在你的for循环中添加了节点后，你也会弹出最近添加的节点，这不是你想要的。因此，您需要在for循环之前移动stack.pop()行。这也是有道理的，因为在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)

您在问题中想要的是什么：

如果，无论出于何种原因（可能正在试验？），你需要做一些你在问题中描述的事情，你可以尝试使用临时的迭代来进行迭代。像这样：

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循环的头部。其余的由你决定。