Advertisement
Iam_Sandeep

Prims Algorithm

Jun 25th, 2022
916
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 0.47 KB | None
  1. import heapq as hq
  2.  
  3. class Solution:
  4.    
  5.     #Function to find sum of weights of edges of the Minimum Spanning Tree.
  6.     def spanningTree(self,n, adj):
  7.         h=[(0,0)]
  8.         ans=0
  9.         vis=set()
  10.         while len(vis)<n:
  11.             w,v=hq.heappop(h)
  12.             if v in vis:continue
  13.             vis.add(v)
  14.             ans+=w
  15.             for u,w in adj[v]:
  16.                 if u not in vis:
  17.                    hq.heappush(h,(w,u))
  18.         return ans
Advertisement
RAW Paste Data Copied
Advertisement