prims
12345678910111213141516171819202122232425262728293031323334
import heapq
def prims(graph):
visit=set()
queue=[]
result=[]
res=0
heapq.heappush(queue,(0,0))
while queue:
wt,u=heapq.heappop(queue)
if u in visit:
continue
else:
visit.add(u)
result.append(wt)
res+=wt
for v,w in graph[u]:
if v not in visit:
heapq.heappush(queue,(w,v))
print(visit)
print(result)
print(res)
graph = {
0: [(1, 2), (2, 3)],
1: [(0, 2), (3, 2), (4, 1)],
2: [(0, 3)],
3: [(1, 2)],
4: [(1, 1)]
}
prims(graph)
Python
INFO