Advertisement
Rakibul_Ahasan

Minimum Spanning Tree( Kruskal's Algorithm)

Dec 9th, 2019
167
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.82 KB | None | 0 0
  1. //#include<iostream>
  2. // #include<algorthem>
  3. #include<bits/stdc++.h>
  4. using namespace std;
  5. #define MX 100
  6.  
  7. struct edgeStructure
  8. {
  9.     int u;
  10.     int v;
  11.     int w;
  12. };
  13.  
  14. bool operator < (edgeStructure lhs , edgeStructure rhs)
  15. {
  16.     return lhs.w < rhs.w;
  17. }
  18.  
  19. bool cmp(const edgeStructure &lhs ,const edgeStructure &rhs)
  20. {
  21.     if(lhs.u != rhs.u)
  22.         return lhs.u < rhs.u;
  23.     else return lhs.w < rhs.w;
  24. }
  25.  
  26. int parent[MX];
  27. int rankParent[MX];
  28.  
  29. vector<edgeStructure> edgeVector;
  30.  
  31. void makeSet(int n)
  32. {
  33.     for(int i=0;i<n;i++){
  34.         parent[i]=i;
  35.         rankParent[i]=0;
  36.     }
  37. }
  38.  
  39. int findParent(int x)
  40. {
  41.     if(x!=parent[x])
  42.         return parent[x]=findParent(parent[x]);
  43.     else return x;
  44. }
  45.  
  46. void unionSet(int x,int y)
  47. {
  48.     int xRoot =findParent(x);
  49.     int yRoot =findParent(y);
  50.  
  51.     if(xRoot==yRoot) return;
  52.  
  53.     if(rankParent[xRoot]<rankParent[yRoot])
  54.         parent[xRoot]=yRoot;
  55.  
  56.     else if(rankParent[xRoot]>rankParent[yRoot])
  57.         parent[yRoot]=xRoot;
  58.  
  59.     else {
  60.         parent[yRoot]=xRoot;
  61.         rankParent[xRoot]++;
  62.     }
  63. }
  64.  
  65. int kruskal(int n)
  66. {
  67.     makeSet(n);
  68.  
  69.     sort(edgeVector.begin(),edgeVector.end());
  70.  
  71.     int sz = edgeVector.size();
  72.  
  73.     int ans=0;
  74.  
  75.     for(int i=0;i<sz;i++){
  76.  
  77.         if(findParent(edgeVector[i].u)!=findParent(edgeVector[i].v))
  78.         {
  79.             /// union
  80.             unionSet(parent[edgeVector[i].u],parent[edgeVector[i].v]);
  81.             //cout<<edgevector[i].u <<" "<<edgevector[i].v<<endl;
  82.             ans+=edgeVector[i].w;
  83.         }
  84.     }
  85.     return ans;
  86. }
  87.  
  88. int main()
  89. {
  90.     int vertex,edge;
  91.     cin>>vertex>>edge;
  92.  
  93.     for(int i=0;i<edge;i++)
  94.     {
  95.         edgeStructure e;
  96.         cin>>e.u>>e.v>>e.w;
  97.         edgeVector.push_back(e);
  98.     }
  99.  
  100.     cout<<"MST Cost "<<kruskal(vertex)<<endl;
  101.  
  102.     return 0;
  103. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement