这个 python 代码的替代方案？

Question

我有一行来自 class 的代码，我没有完全理解它，想要一些更简单的替代方法。它的作用是，使用 weightList，它是一个相互连接的边列表，returns 图中对应值最低的边列表（邻接矩阵）。这是针对 Prim 的最小生成树问题。

edge = sorted(weightList, key=lambda e:graph[e[0]][e[1]])[0];

Answer 1

稍微分解一下就足够了。这个怎么样？

get_edge_weight = lambda e: graph[e[0]][e[1]]
sorted_weights = sorted(weightList, key=get_edge_weight)
edge = sorted_weights[0]

Answer 2

照你说的做：对于所有边，找出图中最小的值。

i, j = current_edge = weightList[0]
current_min = graph[i][j]

for edge in weightList[1:]:
    i, j = edge

    if graph[i][j] < current_min:
        current_min = graph[i][j]
        current_edge = edge

您从 weightList 的第一条边开始，然后迭代所有其他边以尝试找到一个较低的值。当您退出循环时，current_edge 是具有最低值的边缘。

也就是说，尝试理解您的代码可能是值得的。我假设您知道什么 sorted does. To sort your weightList, sorted uses the parameter key, which is a function that returns a value. In your case, your function returns the value in graph at the position of your edge. sorted 将使用此值来比较边缘。

因此，这将对所有边从具有最低值的边到具有最高值的边进行排序。然后，一旦排序，就取第一个元素，即具有最低值的边。

在算法上，使用 sorted for this job isn't a great idea since it has a time complexity of O(n log n). In comparison, my algorithm is O(n) (but probably slower because I assume sorted is implemented in C). Instead, you can obtain the same result in O(n) using standard functions by using min，这当然是所有三个选项中最有效和可读的选项：

edge = min(weightList, key=lambda (i,j): graph[i][j])

Answer 3

如果您希望代码少一些"compact"，这应该可以解决问题：

shortest = weightList[0]

for edge in weightList:
    if graph[edge[0]][edge[1]] < graph[shortest[0]][shortest[1]]:
        shortest = edge

将最短边设置为等于 weightList 中的第一条边，然后遍历列表并查看是否有任何边更短。

Answer 4

在尝试降低复杂性时，我总是寻找将事物分解为不言自明的模块化函数的方法：

def distance(adjacency_matrix, start_node, end_node):
    return adjacency_matrix[start_node][end_node]

sorted_edges = sorted(weightList, key=lambda e: distance(graph, e[0], e[1]))
edge = sorted_edges[0];

这个 python 代码的替代方案？

Alternative to this python code?

python

sorting

minimum-spanning-tree

prims-algorithm