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