1 函数 prim 算法 python

Question

我试图在python中制作1个函数prims算法，但似乎无法正常工作

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)

print [['a'，'b'，1]，['a'，'c'，102]，['b'，'c'，4]，['c'，'c'，'f'，f'，f'，f'，f'，2]，['b'，'f'，1]，['f'，'e'，1]]打印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