python - 按边权重对图进行排序。Python

Question

我有一个格式的元组列表：

(node1, node2, weight)

我想要做的是对这个元组进行排序，以便权重较高的节点位于顶部

例如

(A,B,2)
(A,C,5)
(C,A,2)

应该给我

(A,C,5)
(A,B,2)
(C,A,2)

第一个节点按字母顺序排序。第二个节点按照权重等级递减。

Answer 1

这应该可以正常工作：

lst.sort(key=lambda x:x[2], reverse=True)

当然，我们可以通过以下方式避免 lambda：

import operator
lst.sort(key=operater.itemgetter(2), reverse=True)

如果你想在多个条件下排序，你可以创建有趣的函数来返回元组（元组将按第一个索引排序，然后是第二个，然后是第三个......），或者你可以使用 python 的排序保证稳定的事实。因此，如果您希望列表主要按权重排序，然后按节点名称排序，您只需先按节点名称排序，然后按权重排序。（倒序有点反直觉）。

如果我理解您的问题（在重新阅读并在这里看到一些评论之后），您可以按如下方式完成：

lst.sort(key=lambda x: (-x[2],x[0])) #relying on tuples

这主要按重量排序（首先是高数字），​​然后按字母顺序对具有相同权重的对象按 node1 排序。

请注意，这仅在您可以否定x[2]以使高数字首先出现在排序中时才有效（例如，它不适用于字符串）。完成相同事情的更可靠方法（尽管效率较低？）将是：

lst.sort(key=lambda x: x[0])
lst.sort(key=lambda x: x[2], reversed=True)

Answer 2

使用“关键功能”。由于您希望首先对较大的权重进行排序，因此 key 函数应返回权重的负数，以便较大的权重排序较低。

A='A'
B='B'
C='C'
lst = [(A, B, 2), (A, C, 5), (C, A, 2)]

def weight_key(tup):
    return tup[0], -tup[2], tup[1]

lst.sort(key=weight_key)
print(lst)  # prints: [('A', 'C', 5), ('A', 'B', 2), ('C', 'A', 2)]

编辑：我只是重新阅读了这个问题。我不确定这意味着什么：“所以，第一个节点按字母顺序排序。第二个节点按照权重等级递减。”

但我认为你希望关键是第一，对node1价值进行排序；然后，按重量排序，最大的排序在前；node2然后按值排序。我已经编辑了 key 函数以返回一个以这种方式排序的元组。