代码之家 › 专栏 › 技术社区 › Espoir Murhabazi

获取嵌套列表中项目的级别

nested-lists tree graph python

Espoir Murhabazi · 技术社区 · 7 年前

问题:

我有一些链接数据,我想在这张图片上构建一个这样的结构:

并获得每个项目的级别,因为在将来,我将通过盯着树结构的最低级别进行一些计算。

预期结果:

我需要一个结构,为我提供每个级别的项目:

0级:A
1级:A=B、C、D
2级:D=E、F、G
3级:E=H、I、J、K

到目前为止,我已经尝试了:

我已经尝试了这个递归代码来模拟行为,但我无法获得项目级别的项目。

dict_item = {"A": ["B","C","D"], "D": ["E","F","G"], "E":["H","I","J"]}
def build_bom(product):
    if not dict_item.get(product):
        return product
    else :
        return [build_bom(x) for x in dict_item.get(product)]
print(build_bom("A"))

我的输出是一个嵌套列表,如下所示:

['B', 'C', [['H', 'I', 'J'], 'F', 'G']]

我的问题:

我不确定这是否是处理我的问题的最佳方法。以下是所需的输出:

[ {"parent_E":["H", "I", "J"]}, 
{"parent_D": ["E", "F", "G"]},
{"parent_A"} :["D","C","B"]},
]

字典列表(其中键是父项,值是子项),列表中的第一个元素是我的结构的最低级别,最后一个是最高级别的元素。

PS:这是一个模拟,但在将来,我将不得不使用此代码处理大型数据集。任何帮助都将不胜感激

1 回复 | 直到 5 年前

codelessbugging 7 年前

这就是我将如何处理这个问题。首先,我将从 dict_item 对象

dict_item = {"A": ["B","C","D"], "D": ["E","F","G"], "E":["H","I","J"]}

def build_tree(x):
    if x in dict_item:
        return {x: [build_tree(v) for v in dict_item[x]]}
    else:
        return x

tree = build_tree("A")
print(tree)
>>> {'A': ['B', 'C', {'D': [{'E': ['H', 'I', 'J']}, 'F', 'G']}]}

然后,在树上进行广度优先搜索。每次我们点击一个有子元素的元素时,都会将其附加到一个列表中:

results = []
queue = [tree]

while queue:
    x = queue.pop(0)
    if isinstance(x, dict):
        parent, children = list(x.items())[0]
        results.append({'parent_' + parent: dict_item[parent]})
        for child in children:
            queue.append(child)

print(results)
>>> [{'parent_A': ['B', 'C', 'D']}, {'parent_D': ['E', 'F', 'G']}, {'parent_E': ['H', 'I', 'J']}]

那么我们现在需要做的就是颠倒列表:

print list(reversed(results))
>>> [{'parent_E': ['H', 'I', 'J']}, {'parent_D': ['E', 'F', 'G']}, {'parent_A': ['B', 'C', 'D']}]