如何用Python按权重对带权无向图的邻接表进行排序？

问题描述 #

我有一个带权无向图的邻接表：

graph_G = {'A': [('B', 7), ('E', 2)], 'B': [('C', 6)], 'C': [('A', 5), ('D', 3)], 'D': [('E', 1)], 'E': [('A', 7)], }

我想把每个节点对应的邻接列表按边的权重（也就是元组的第二个元素）进行升序排序，期望得到的结果是：

graph_G = {'A': [('E', 2), ('B', 7)], 'B': [('C', 6)], 'C': [('D', 3), ('A', 5)], 'D': [('E', 1)], 'E': [('A', 7)], }

我尝试过这段代码：

print("Sort Dict %s" % (sorted(graph_G.items(), key=itemgetter(1))))

但它是对字典的键值对按元组第一个元素排序，不符合我的需求，请问该怎么实现？

解决方案 #

你需要的是对每个节点的邻接边列表单独排序，而不是对整个字典的键值对排序。原代码的问题在于它把整个字典的items作为排序对象，而我们要操作的是每个item中的value（邻接列表）。

这里有两种常用的实现方式：

方式1：创建新的排序后字典（推荐，不修改原数据） #

使用字典推导式遍历原字典的每个键值对，对每个邻接列表调用sorted()函数，指定排序依据为边的权重（元组第二个元素）：

# 可选：如果喜欢用itemgetter而不是lambda，可以导入它
from operator import itemgetter

graph_G = {'A': [('B', 7), ('E', 2)], 'B': [('C', 6)], 'C': [('A', 5), ('D', 3)], 'D': [('E', 1)], 'E': [('A', 7)], }

# 用lambda指定排序键
sorted_graph = {node: sorted(edges, key=lambda x: x[1]) for node, edges in graph_G.items()}

# 或者用itemgetter，效果一致
# sorted_graph = {node: sorted(edges, key=itemgetter(1)) for node, edges in graph_G.items()}

print(sorted_graph)

运行后输出的结果就是你期望的：

{'A': [('E', 2), ('B', 7)], 'B': [('C', 6)], 'C': [('D', 3), ('A', 5)], 'D': [('E', 1)], 'E': [('A', 7)]}

方式2：直接修改原字典 #

如果你不需要保留原字典的结构，可以直接遍历原字典，对每个节点的邻接列表调用sort()方法（原地排序）：

from operator import itemgetter

graph_G = {'A': [('B', 7), ('E', 2)], 'B': [('C', 6)], 'C': [('A', 5), ('D', 3)], 'D': [('E', 1)], 'E': [('A', 7)], }

for node in graph_G:
    # 原地排序，直接修改原字典的邻接列表
    graph_G[node].sort(key=lambda x: x[1])
    # 同样可以替换为itemgetter(1)
    # graph_G[node].sort(key=itemgetter(1))

print(graph_G)

关键说明 #

• sorted()和sort()的key参数用于指定排序的依据，这里lambda x: x[1]表示取每个边元组的第二个元素（权重）作为排序关键字。
• 默认排序是升序，如果需要降序，可以添加reverse=True参数，比如sorted(edges, key=lambda x: x[1], reverse=True)。

内容的提问来源于stack exchange，提问作者Lalit