替代这个python代码？

Question

我有一行代码，我不完全理解，并希望一些更容易的替代。这是做什么的，使用weightList，它是一个相互连接的边的列表，并从图（邻接矩阵）中返回具有最低相应值的边列表。这是针对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做什么。要对weightList进行排序，sorted使用参数key，该参数是一个返回值的函数。在你的情况下，你的函数在你的边缘位置返回的值。 sorted将使用此值来比较边缘。

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

在算法上，使用sorted这个工作并不是一个好主意，因为它的时间复杂度为O(n log n)。相比之下，我的算法是O(n)（但可能更慢，因为我认为sorted在C中实现）。相反，您可以通过使用min，这当然是最有效和最可读的选择了三个所有获得使用标准功能O(n)相同的结果：

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

Answer 3

如果你想要的代码是一个少一点“紧凑”，这应该做的伎俩：

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];