如何对依赖项列表排序

Question

有没有任何python方法可以将无序的链接列表排序为依赖关系排序的列表？在

给出以下无序的“链接”列表：

unordered_linked_list = [
    {id: "DE3", pred: "FE8"}, 
    {id: "FE8", pred: None}, 
    {id: "79E", pred: "DE3"}, 
    {id: "52D", pred: "79E"},
    ...
]

这会导致

^{pr2}$

Answer 1

通常，排序依赖项是用topological sort完成的。然而，这个特定的情况足够简单（每个项目都有一个传入和输出边），不需要完全拓扑排序。

您所拥有的不是链接列表，而是链接列表。所以，只要将其重新构造成类似链接列表的内容并遍历它：

# transform into a source:target dictionary
links = {d['pred'] if d['pred'] else 'root':d['id'] for d in unordered_linked_list}

# follow links and print
source = 'root'
while source in links:
    print links[source]
    source = links[source]

Answer 2

试试这个：

unordered_linked_list = [
    {'id': "DE3", 'pred': "FE8"}, 
    {'id': "FE8", 'pred': None}, 
    {'id': "79E", 'pred': "DE3"}, 
    {'id': "52D", 'pred': "79E"},
]

def traverse(links):
    preds = dict()
    for item in links:
        preds[item['pred']] = item['id']
    item = None
    items = []
    while item in preds:
        item = preds[item]
        items.append(item)
    return items

>>> traverse(unordered_linked_list)
['FE8', 'DE3', '79E', '52D']