1功能Prim算法蟒蛇

我試圖讓Python中的1個功能普里姆算法，但它似乎並不奏效1功能Prim算法蟒蛇

def prim(edges): 
    inGraph = ['A'] 
    discovered = [] 
    results = [] 
    counter = 0 
    while True: 
      tmplist = [] 
      for i in edges: 
        if inGraph[counter] in i: 
          discovered.append(i) 
          tmplist.append(i) 
      for i in tmplist: 
        edges.remove(i) 
      tmp = [] 
      for i in discovered: 
        tmp.append(i[2]) 
      mini = tmp.index(min(tmp)) 
      alpha = discovered[mini][0] 
      beta = discovered[mini][1] 

      if alpha not in inGraph or beta not in inGraph: 
        if alpha in inGraph: 
          inGraph.append(beta) 
        elif beta in inGraph: 
          inGraph.append(alpha) 
        results.append(discovered[mini]) 
      discovered.pop(mini) 
      if discovered == []: 
        break 
      counter+=1 

    return (inGraph, results)

打印[ 'A'， 'B'，1]，[ 'A'，'C'，102]，['B'，'C'，4]，['C'，'F'，2]，['B'，'F'，1]，['F ''，'E'，1]] print prim（[['A'，'B'，1]，['A'，'C'，102]，['B'，'C'，4]， ['C'，'F'，2]，['B'，'F'，1]，['F'，'E'，1]]）

問題在於發現某處， if語句檢查是否爲空或從中刪除元素。我只是不知道該把它放在哪裏

來源

2017-02-21 Sigma 7

決不**改變列表，而你遍歷它**：不要叫'edges.remove（..）'，而你遍歷它。 –

此外，你的算法效率很低。 –

效率並不重要，它不是編輯通過for循環 –

想象一下只有一個頂點與'A'連接，說'B'。所以，在第一次迭代中，你將只能發現一條邊。在向inGraph添加'B'之後，您只會彈出發現的邊緣。

因此，您發現的== []變爲true並且循環中斷，即使可能還有與'B'連接的千邊。

要終止主循環，計算頂點no並斷開len（inGraph）== no_of_vertex。

要做到這一點，您可以：

V = set() 
for e in edges: 
    v.add(e[0]) 
    v.add(e[1]) 
no_of_vertex = len(V) 
V = None #To help garbage collector

來源

2017-02-21 16:06:41

因此，我在哪裏把if語句或'discovered.pop（迷你）' –

這隻會被添加到函數的結尾附近？ –

我把它在年底得到這個錯誤 '回溯（最近通話最後一個）：文件「prim.py」，第40行，在印刷古板（[ 'A'， 'B'，1 ]，['A'，'C'，102]，['B'，'C'，4]，['D'，'B'，7]，['D'，'F'，240]， ['C'，'F'，2]，['B'，'F'，1]，['F'，'E'，1]]）文件「prim.py」，第17行，在prim mini = tmp.index（min（tmp）） ValueError：min（）arg是一個空序列，在while循環開始之前函數的開始處爲 –

1功能Prim算法蟒蛇

回答

相關問題