1函数prim的算法python
1函数prim的算法python
提问于 2017-02-21 23:48:22
我试着用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'，'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])
问题出在discovered的某个地方，要么是if语句检查它是否为空，要么是从中删除一个元素。我只是不知道该把它放在哪里
回答 1
Stack Overflow用户
发布于 2017-02-22 00:06:42
假设只有一个顶点与“A”相连，也就是“B”。因此，在第一次迭代中，您将只有一条边处于已发现状态。将'B‘添加到inGraph之后，您将从discovered中弹出唯一的边。
所以你发现的== []会变成真，循环会中断，即使可能还有上千条边与'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页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/42371901
复制相关文章
相似问题
腾讯云开发者
