python - 按实际列表的值对 python 中的字典进行排序

Question

如果我得到一个表示图的字典，其中顶点是键，值是列表，其条目包含相邻顶点和两个顶点之间的权重，我如何返回递增顺序的边列表没有重复？例如，我可能会得到以下字典...:

{"A": [["B",10], ["D",5]], "B": [["A",10], ["C",5]], "C": [["B",5],["D",15]], "D": [["C",15], ["A",5]]}.

此外，我只被允许导入副本库，因此我可以复制一个列表并使用 deepcopy() 创建一个具有相同元素的新对象。

现在，我正在尝试将字典转换为列表，因为我认为对列表中的元素进行排序并删除重复边可能更容易。所以目前我有以下内容(图表是字典，在本例中是我上面提供的字典)...

def edge_get(graph):

    input_list = []
    sorted_list = []

    for key, value in graph.items():
        temp = [key,value]
        input_list.append(temp)

    print(input_list)

这打印出来...

[['A', [['B', 10], ['D', 5]]], ['B', [['A', 10], ['C', 5]]], ['C', [['B', 5], ['D', 15]]], ['D', [['C', 15], ['A', 5]]]]

我想让它输出:

[['A', 'B', 10], ['A', 'D', 5], ['B', 'A', 10], ['B', 'C', 5],...

我想如果我能这样得到它，我可以比较每个列表的第三个元素，在列表中，如果它们相同，检查其他元素是否匹配(相同的边缘)。基于此，我可以将它添加到最终列表中，或者忘记它并继续前进。

对于这个例子，最终目标是:

[['A', 'D'], ['B', 'C'], ['A', 'B'], ['C', 'D']]

Answer 1

所以你有一个将图表示为邻接列表的字典，你想将该邻接列表转换为边列表。

您可以使用嵌套列表理解来做到这一点:

graph = {"A": [["B",10], ["D",5]], "B": [["A",10], ["C",5]], "C": [["B",5],["D",15]], "D": [["C",15], ["A",5]]}
edges = [(src, dst, weight) for src, adjs in graph.items() for dst, weight in adjs]
# edges = [('A', 'B', 10), ('A', 'D', 5), ('B', 'A', 10), ('B', 'C', 5), ('C', 'B', 5), ('C', 'D', 15), ('D', 'C', 15), ('D', 'A', 5)]

然后您可以通过转换为字典来消除重复边，请注意，如果您有权重冲突的重复边，这将任意选择一个权重:

uniques = {frozenset([src, dst]): weight for src, dst, weight in edges}
# uniques = {frozenset({'B', 'A'}): 10, frozenset({'A', 'D'}): 5, frozenset({'B', 'C'}): 5, frozenset({'C', 'D'}): 15}

然后用sorted对边进行排序:

sorted_uniques = sorted(uniques.items(), key=lambda v: v[1])
# sorted_uniques = [(frozenset({'A', 'D'}), 5), (frozenset({'C', 'B'}), 5), (frozenset({'A', 'B'}), 10), (frozenset({'C', 'D'}), 15)]

最后，要获得所需结构的结果，您只需执行以下操作:

result = [sorted(e) for e, weight in sorted_uniques]
# result = [['A', 'D'], ['B', 'C'], ['A', 'B'], ['C', 'D']]