我有一个(可能)简单的图遍历问题。我是一个图形新手,使用 networkx 作为我的图形数据结构。我的图表总是看起来像这样:
0
1 8
2 3 9 10
4 5 6 7 11 12 13 14
我需要返回从根节点到给定节点的路径(例如,path(0, 11)
应该返回 [0, 8, 9, 11]
).
我有一个解决方案,它通过传递一个列表来工作,该列表会增长和缩小以跟踪您遍历树时路径的样子,最终在找到目标节点时返回:
def VisitNode(self, node, target, path):
path.append(node)
# Base case. If we found the target, then notify the stack that we're done.
if node == target:
return True
else:
# If we're at a leaf and it isn't the target, then pop the leaf off
# our path (backtrack) and notify the stack that we're still looking
if len(self.neighbors(node)) == 0:
path.pop()
return False
else:
# Sniff down the next available neighboring node
for i in self.neighbors_iter(node):
# If this next node is the target, then return the path
# we've constructed so far
if self.VisitNode(i, target, path):
return path
# If we've gotten this far without finding the target,
# then this whole branch is a dud. Backtrack
path.pop()
我从骨子里觉得没有必要绕过这个“路径”列表……我应该能够使用调用堆栈跟踪该信息,但我不知道如何……有人可以启发我如何使用堆栈来跟踪路径递归地解决这个问题吗?
最佳答案
您可以通过在失败时返回 None
并在成功时返回部分路径来避免绕过路径。通过这种方式,您不会保留从根到当前节点的某种“面包屑痕迹”,但如果找到它,您只会构建一条从目标返回根的路径。未经测试的代码:
def VisitNode(self, node, target):
# Base case. If we found the target, return target in a list
if node == target:
return [node]
# If we're at a leaf and it isn't the target, return None
if len(self.neighbors(node)) == 0:
return None
# recursively iterate over children
for i in self.neighbors_iter(node):
tail = self.VisitNode(i, target)
if tail: # is not None
return [node] + tail # prepend node to path back from target
return None #none of the children contains target
我不知道您使用的图形库,但我假设即使是叶子也包含 neighbours_iter
方法,这显然不应该为叶子产生任何 child 。在这种情况下,您可以省略对叶子的显式检查,使其更短一些:
def VisitNode(self, node, target):
# Base case. If we found the target, return target in a list
if node == target:
return [node]
# recursively iterate over children
for i in self.neighbors_iter(node):
tail = self.VisitNode(i, target)
if tail: # is not None
return [node] + tail # prepend node to path back from target
return None # leaf node or none of the child contains target
我还删除了一些 else
语句,因为在 if
的 true-part 中你是从函数返回的。这是常见的 refactering pattern (有些老派的人不喜欢)。这会删除一些不必要的缩进。
关于python - 查找树中两个节点之间的(保证唯一的)路径,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/19071645/