多路树和结构

Question

我有一个应用数学问题，几乎可以完美地映射到寻找多路树中的最长路径。

我有一个函数 child() 可以给出子节点（space 中满足条件的点）。唯一需要注意的是 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)

但在这一点上，我不确定要做什么 return。我基本上想映射整个多路树，直到我到达所有内容的叶子。有什么想法或提示吗？谢谢大家。

编辑：

更新 1：为了完整起见，我勾勒出一个粗略的输入 child() 需要什么： https://i.imgur.com/3MkfsYc.png 基本上找到箭头标记的节点的子节点 child() 需要列表根和节点本身之间的节点数，即标有红点的节点。

更新 2：

我已经编写了如下的 child(node)，我目前正在研究它 --

def pathwalk(node):

    children = child(node)
    paths = [child(node.append(kid)) for kid in children]

    return paths

Answer 1

你可以做这样的事情来获得最长的路径。在这里它为您提供了一个节点列表，您可以从那里提取任何相关信息：

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

不处理平局，而是任意选择一个选项。

（注：半测试）

Answer 2

我想我已经找到问题所在。因为我想保留一个运行列表，其中包含您找到的所有节点的子节点（您跟踪您走过的路径，请参见 imgur pic）。我通过添加

编辑了 Illuvatar 的例程

children_vals = [longest_path(node+[c]) for c in children]

通过这种方式，您可以递归地将每个父项与其子项连接起来。

多路树和结构

Multiway trees and structures

python

data-structures

multiway-tree