Алгоритм 1 функции прим

Question

Я попытался сделать алгоритм 1 функции prims в 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]])

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

Answer 1

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

Таким образом, ваше обнаруженное == [] становится истинным и разрывы цикла, даже если там может быть тысяча ребер, связанных с 'B'.

Чтобы завершить основной цикл, вычислите число вершин и прервите, если 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