Iam_Sandeep

kruskolls algorithm mst

Jul 25th, 2021
1,092
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. Given a weighted, undirected and connected graph of V vertices and E edges. The task is to find the sum of weights of the edges of the Minimum Spanning Tree.
  2.  
  3.  
  4. from collections import deque
  5. class Solution:
  6.    
  7.    
  8. #Function to find sum of weights of edges of the Minimum Spanning Tree.
  9.     def spanningTree(self, v, d):
  10.         def find(u):
  11.             if parent[u]!=u:
  12.                 parent[u]=find(parent[u])
  13.                 return parent[u]
  14.             else:
  15.                 return u;
  16.         parent=[i for i in range(v)]
  17.         rank=[0 for i in range(v)]
  18.         adj=deque()
  19.         for i in range(v):
  20.             for j in d[i]:
  21.                 adj.append([i,j[0],j[1]])
  22.         adj=sorted(adj,key=lambda x:x[2])
  23.         edges=0
  24.         weight=0
  25.         for i in adj:
  26.             x=i[0]
  27.             y=i[1]
  28.             w=i[2]
  29.             p=find(x)
  30.             q=find(y)
  31.             if edges<v-1:
  32.                 if p!=q:
  33.                     #print("hai")
  34.                     if rank[p]>rank[q]:
  35.                         parent[p]=q
  36.                     elif rank[p]<rank[q]:
  37.                         parent[q]=p
  38.                     else:
  39.                         parent[p]=q
  40.                         rank[p]+=1
  41.                     edges+=1
  42.                     weight+=w
  43.         return weight
  44.                
  45.         #code here
  46.  
  47. #{
  48. #  Driver Code Starts
  49. #Initial Template for Python 3
  50. import atexit
  51. import io
  52. import sys
  53.  
  54. # Contributed by : Nagendra Jha
  55.  
  56. if __name__ == '__main__':
  57.     test_cases = int(input())
  58.     for cases in range(test_cases):
  59.         V,E = map(int,input().strip().split())
  60.         adj = [[] for i in range(V)]
  61.         for i in range(E):
  62.             u,v,w = map(int,input().strip().split())
  63.             adj[u].append([v,w])
  64.             adj[v].append([u,w])
  65.         ob = Solution()
  66.        
  67.         print(ob.spanningTree(V,adj))
  68. # } Driver Code Ends
RAW Paste Data