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

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 source

dict_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']]