基于源-目的字典计算源路径

Question

我有一个输入字典 -dict_input目标为keys，源为values。一个目的地可以有一个或多个来源。dict_input = {'C411':['C052'],'C052':['C001','C002'], 'C001':['9001'], 'C002':['9002']}在上面dict_input，终端目的地是，C411而初始来源是9001和9002。我正在尝试为终端目的地提出源路径C411。预期输出形式为list-[['C411', 'C052', 'C001', '9001'], ['C411', 'C052','C002', '9002']]我有这个代码：def get_source(node, dict_input, source=[]):    if node in dict_input:        source.append(node)        for i in dict_input[node]:            if i != node:                get_source(i, dict_input, source)            else:                source.append(node)    else:        source.append(node)        return source    return sourcedict_input = {'C052':['C001','C002'], 'C411':['C052'], 'C001':['9001'], 'C002':['9002']} print(get_source('C411', dict_input, []))输出是合并成一个列表的两个源路径 -['C411', 'C052', 'C001', '9001', 'C002', '9002']如何修改我的代码以获取每个源路径的单独列表？

Answer 1

pop完成访问节点后不要忘记从当前路径

如果遇到“叶子”（不是键的节点 ID），则在输出列表中存储当前路径的副本

警惕损坏的数据，例如循环链接 - 将有助于保留set访问过的节点

上面的示例实现：

def get_source(root, dict_input):

    # output list

    path_list = []

    # current path

    cur_path = []

    # visited set

    visited = set()

    # internal recursive helper function

    def helper(node):

        cur_path.append(node)

        # normal node

        if node in dict_input:

            if not node in visited:

                visited.add(node)

                for child in dict_input[node]:

                    helper(child)

            # else: cycle detected, raise an exception?

        # leaf node

        else:

            # important: must be a copy of the current path

            path_list.append(list(cur_path))

        cur_path.pop()

    # call this helper function on the root node

    helper(root)

    return path_list

测试：

>>> dict_input = {'C411':['C052'],'C052':['C001','C002'], 'C001':['9001'], 'C002':['9002']}

>>> get_source('C411', dict_input)

[['C411', 'C052', 'C001', '9001'], ['C411', 'C052', 'C002', '9002']]