我试图在python创建的图类上进行深度优先的递归搜索。由于某种未知的原因AssertionError: None not found in [[1, 2, 4, 6], [1, 2, 4, 7, 6]]
,我在声明级别的测试失败了:,我了解该错误的含义,并且我不会直接询问该算法,而是询问其他问题。
我决定使用VS Code python调试器检查运行中的代码,并注意到随着每个新调用将新的堆栈帧推入堆栈(参见图片),它们为“已访问”(设置)和“路径”共享相同的值'(列出)实例(完全意外和令人困惑)。我添加了一个callnumber虚拟变量作为健全性检查,以确保我正确地使用了调试器。
我不知道为什么我没有早点了解它,特别是因为我已经在C和内存管理方面做了很多工作。这些对象显然是放在堆上并通过引用传递的,因此不是真正的独立实例,对吗?
有什么方法可以使这些基于堆栈的变量?我知道不建议这样做,因为这可能会导致堆栈溢出(没有双关语),也不会充分利用空间。
现在我了解了所发生的事情,我想知道您是否有一些关于如何使该算法运行的指针(这次是双关语),因为这种方法由于基于堆而无法工作?我不需要解决它,只需一些提示或线索,就可以产生更深刻的想法。
顺便说一句,我一直在努力提高阅读和理解文档的能力。我喜欢将文档作为我的第一篇文章,但是当我用python搜索某些东西时,与其他语言不同,它们总是接近过去的随机教程。我刚刚进入了内置类型的官方页面,并搜索了堆或内存之类的单词以获取列表和字典,但没有找到任何解释这些对象的位置,它们如何增长或调整大小的信息,尽管它可能如此明显对经验丰富的程序员而言是隐式的,但是无论如何,这是我的代码
class Graph:
def __init__(self):
self.vertices = {}
def add_vertex(self, vertex_id):
self.vertices[vertex_id] = set()
def add_edge(self, v1, v2):
self.vertices[v1].add(v2)
# more functions
def dfs_recursive(self, starting_vertex, destination_vertex, visited = set(), path=[]):
"""
Return a list containing a path from
starting_vertex to destination_vertex in
depth-first order.
This should be done using recursion.
"""
result = None
path.append(starting_vertex)
visited.add(starting_vertex)
if starting_vertex == destination_vertex:
return path
for neighbor in self.vertices[starting_vertex]:
if neighbor not in visited:
visited.add(neighbor)
result = self.dfs_recursive(neighbor, destination_vertex, visited, path, callnumber+1)
return result
编辑:由于rioV8的输入,解决了算法。这是我的代码
def dfs_recursive(self, starting_vertex, destination_vertex, visited = None, path=None, callnumber=1):
path = path or []
visited = visited or set()
path.append(starting_vertex)
visited.add(starting_vertex)
if starting_vertex == destination_vertex:
return path
for neighbor in self.vertices[starting_vertex]:
if neighbor not in visited:
result = self.dfs_recursive(neighbor, destination_vertex, visited.copy(), path[:], callnumber+1)
if result is not None and result[-1] == destination_vertex:
return result
return None
不要将可修改对象用作函数默认参数。
它们是在函数编译时创建的,而不是在函数调用时创建的。并被重用于每个呼叫。
None
在函数内部使用并创建可修改的。
并在递归调用中制作可修改的副本。
def dfs_recursive(self, starting_vertex, destination_vertex, visited=None, path=None):
visited = visited or set()
path = path or []
# rest of function
result = self.dfs_recursive(neighbor, destination_vertex, visited.copy(), path[:], callnumber+1)
本文收集自互联网,转载请注明来源。
如有侵权,请联系[email protected] 删除。
我来说两句