Iam_Sandeep

kruskolls algorithm mst

Jul 25th, 2021 (edited)
1,261
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 1.54 KB | None | 0 0
  1. #User function Template for python3
  2.  
  3. class Solution:
  4.     #Function to find sum of weights of edges of the Minimum Spanning Tree.
  5.     def spanningTree(self, n, d):
  6.         def find(u):
  7.             if parent[u]==u:
  8.                 parent[u]=u
  9.                 return u
  10.             else:
  11.                 #path compression
  12.                 parent[u]=find(parent[u])
  13.                 return parent[u]
  14.                
  15.         def union(a,b):
  16.             x=find(a)
  17.             y=find(b)
  18.            
  19.             if x==y:
  20.                 return False
  21.         #union by rank
  22.         #if ranks of two nodes are same then rank of unified set will be incremented by 1 else rank remains unchanged
  23.             elif rank[x]==rank[y]:
  24.                 rank[y]+=1
  25.                 parent[x]=y
  26.              
  27.             elif rank[x]<rank[y]:
  28.                 parent[x]=y
  29.             else:
  30.                 parent[y]=x
  31.             return True
  32.            
  33.         e=[]
  34.         ans=0
  35.         for i in range(n):
  36.             for j,k in d[i]:
  37.                 e.append((i,j,k))
  38.         e.sort(key=lambda x:x[2])
  39.         c=0
  40.         #initialisation steps vvimp
  41.         rank=[0]*n
  42.         parent=[i for i in range(n)]
  43.        
  44.         for a,b,w in e:
  45.             #do process till we get sufficient edges
  46.             if c<n-1:
  47.                 #if union ==False means by adding (a,b) results a cycle
  48.                 if union(a,b):
  49.                     ans+=w
  50.                     c+=1
  51.             else:break
  52.         return ans
  53.  
  54.  
  55.  
  56.            
  57.            
  58.        
  59.        
  60.        
  61.    
Add Comment
Please, Sign In to add comment