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

Question

我想在树中找到元素的完整路径。元素可以位于几个地方。树我目前的代码：levels = [    {"L3A": ["L4A"]},    {"L3B": ["L4B"]},    {"L3C": ["L4C"]},    {"L1": ["L2", "L4A"]},    {"L2": ["L3A", "L3B", "L3C"]}]def get_level(name):    tree = []    recursive(name, tree)    return treedef 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 > L3AL4A 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 N

let 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 paths

print(find_reverse_path("L4A"))

输出：

[['L1', 'L4A'], ['L1', 'L2', 'L3A', 'L4A']]

这是一个迭代 DFS。（我认为，如果路径在递归 DFS 中扩展，我们会更难知道。）

看看这两行，它们包含了“技巧”：

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

请注意，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 paths

4. paths = [[L1, L4A], [L3A, L4A]]

5. paths = [[L1, L4A]], path = [L3A, L4A]

...

如果我们不制作副本，并且如果我们发现当前路径的头部有几条边，我们将在步骤 4 中找到paths = [[L3A, L1, L4]]。这几乎与您在代码中遇到的问题相同。

Answer 2

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