在树中查找元素的完整路径

Question

我想在树中找到元素的完整路径。元素可以位于几个地方。

树

我目前的代码：

levels = [

    {"L3A": ["L4A"]},

    {"L3B": ["L4B"]},

    {"L3C": ["L4C"]},

    {"L1": ["L2", "L4A"]},

    {"L2": ["L3A", "L3B", "L3C"]}

]

def get_level(name):

    tree = []

    recursive(name, tree)

    return tree

def recursive(name, tree):

    for level in levels:

        for k, v in level.items():

            if name in v:

                tree.append(k)

                recursive(k, tree)

levl = get_level("L4A")

print(levl)

结果

是： ['L3A', 'L2', 'L1', 'L1']

想： [['L3A', 'L2', 'L1'], ['L1']]

最终想要：

L4A in L1 > L2 > L3A

L4A in L1 

你能给我一些建议如何改变它吗？

Answer 1

为什么L1在您的列表中出现两次？因为您有两条通向L4A:L1 -> L2 -> L3A -> L4A和 的路径L1 -> L4A，但只有一个path变量来存储这些路径。由于您使用一种反向DFS，因此您具有级别：L4 -> L3A -> L2 -> L1，然后L4 -> L1。让我们尝试详细说明一个算法。您正在处理一个图（如果您添加一个根，您将得到一棵树），因此我将使用通常的词汇：级别是“节点”，级别之间的路径是“边”。这是一个很好的方法：给定：一个节点 N找到所有节点P，使边P-N存在并存储路径。对于 each P，找到所有节点Q，使边P-Q存在并存储路径。一旦没有更多edge的节点Q，即当前path最大，返回path.作为一个真正的算法，它缺乏一点精度。我们重点说一下：GIVEN: a node Nlet paths_to_explore = [N]while paths_to_explore is not empty:    for every path_to_explore:        try to add a node at the beginning of path_to_explore        if it fails, yield path_to_explore在我开始编写代码之前，请注意您对图形的表示不是两种常用的表示。在您的情况下，您有边缘列表，但字典from_node -> [to_nodes]更好：edges = {    "L3A": {"L4A"},    "L3B": {"L4B"},    "L3C": {"L4C"},    "L1": {"L2", "L4A"},    "L2": {"L3A", "L3B", "L3C"},}这使得边上的迭代更容易：for from_node, to_nodes in edges.items():    # do something with nodes现在，代码：def find_reverse_path(name):    paths = []    paths_to_explore = [[name]]    while paths_to_explore:        path = paths_to_explore.pop() # next!        to_node = path[0] # the HEAD of the current path        expanded = False        for from_node, to_nodes in edges.items():            if to_node in to_nodes: # there's an edge to the HEAD                new_path_to_explore = [from_node] + path # new path = from_node + old path                paths_to_explore.append(new_path_to_explore) # add it to the exploration list                expanded = True # this path was expanded        if not expanded: # the path is maximal            paths.append(path) # use yield if you want to create a generator    return pathsprint(find_reverse_path("L4A"))输出：[['L1', 'L4A'], ['L1', 'L2', 'L3A', 'L4A']]这是一个迭代 DFS。（我认为，如果路径在递归 DFS 中扩展，我们会更难知道。）看看这两行，它们包含了“技巧”：new_path_to_explore = [from_node] + path # new path = from_node - old pathpaths_to_explore.append(new_path_to_explore) # add it to the exploration list请注意，new_path_to_explore是复制的path，这意味着我们不只是增加一个节点paths[-1]（到位）。这是为什么？看第一步：1. paths = [[L4A]]2. paths = [], path = [L4A]3. append L1-L4A to paths, then append L3A-L4A to paths4. paths = [[L1, L4A], [L3A, L4A]]5. paths = [[L1, L4A]], path = [L3A, L4A]...如果我们不制作副本，并且如果我们发现当前路径的头部有几条边，我们将在步骤 4 中找到paths = [[L3A, L1, L4]]。这几乎与您在代码中遇到的问题相同。

Answer 2

反转关联图，然后应用标准图搜索，例如。DFS。