# 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)]
19.         for i in range(v):
20.             for j in d[i]:
23.         edges=0
24.         weight=0
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())