替代這個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];