我在应用数学中遇到一个问题,该问题几乎可以完美地映射到在多路树中查找最长路径。
我有一个函数 child() ,它给出子节点(空间中满足条件的点)。唯一需要注意的是 child() 需要连接到它的所有先前节点,包括根节点。正是在这里,我正在努力递归地编写代码。到目前为止,我有类似下面的内容。
def multitree(node):
tmp_list = child(node)
for child2 in tmp_list:
if len(child(child2)))==0: #if you hit a leaf (dead end), go to next element
continue
else:
multitree(child2)
但此时,我不确定要返回什么。我本质上想映射整个多路树,直到我到达所有东西的叶子。有什么想法或建议吗?谢谢大家。
编辑:
更新 1:为了完整起见,我概述了输入 child() 需要什么的粗略想法:/image/QDyNj.png基本上,要找到箭头 child() 标记的节点的子节点,需要 root 和节点本身之间的节点列表,即用红点标记的节点。
更新2:
我已经编写了 child(node) 如下,我目前正在研究它 --
def pathwalk(node):
children = child(node)
paths = [child(node.append(kid)) for kid in children]
return paths
最佳答案
你可以这样做来获得最长的路径。它在这里为您提供节点列表,您可以从那里提取任何相关信息:
def longest_path(node):
children = child(node)
if not children: # leaf node
return [node]
children_vals = [longest_path(c) for c in children]
longest = max(children_vals, key=len)
return [node] + longest
不处理关系,或者更确切地说,任意选择一个选项。
(注:半测试)
关于python - 多路树和结构,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/41082172/