1 функция алгоритм питон Прима

Question

я попытался сделать 1 функцию примы алгоритм в Python, но не кажется, что это будет работать

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

проблема лежит где-то с обнаруженными если оператор проверяет, является ли он пустым или удаляет из него элемент. Я просто не знаю, где поставить

Answer 1

Предположим, что только одна вершина связана с 'A', например 'B'. Итак, на первой итерации у вас будет только одно преимущество в обнаружении. После добавления «B» в inGraph вы выпадаете, только из обнаруженного края.

Таким образом, ваш обнаруженный == [] становится истинным и прерывается петлями, хотя все еще могут быть тысячи ребер, связанных с «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