我一直在练习算法和数据结构。我正在尝试编写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/

10-10 09:23