有缺陷的迭代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()

但是它不起作用，因为我无法在更改循环底部的tos时动态更新循环nextVertex in tos.getConnections():。你知道吗

你怎么解决这个问题？我知道我可以用递归来做，但我想要一个接近我的版本的迭代解决方案。你知道吗

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)

你想问的是：

如果，出于什么原因（可能是实验？），您需要做一些您在问题中描述的事情，您可以尝试使用临时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循环的头。剩下的就看你了。你知道吗